Binary Search Tree

Binary Search Trees (BSTs) are a fundamental data structure in computer science...

Binary Search Trees (BSTs) are a fundamental data structure in computer science. They are used to store and manage data efficiently, allowing for quick insertion, deletion, and search operations. BSTs play a crucial role in various applications, from databases to network routing algorithms, due to their structured and hierarchical nature.

Basic Concepts

Node Structure

In a Binary Search Tree, each element is stored in a node. A node contains three main components:

• Value: The data stored in the node.
• Left Child: A pointer/reference to the left child node, which contains values less than the parent node.
• Right Child: A pointer/reference to the right child node, which contains values greater than the parent node.

Properties of a BST

• Left Subtree: Contains only nodes with values less than the parent node.
• Right Subtree: Contains only nodes with values greater than the parent node.
• No Duplicate Nodes: Typically, BSTs do not contain duplicate values to maintain uniqueness.

Binary Search Tree Operations

Insertion

To insert a new value in a BST, follow these steps:

1. Start from the root node.
2. Compare the new value with the current node's value.
3. If the new value is less, move to the left child.
4. If the new value is greater, move to the right child.
5. Repeat steps 2-4 until you find an appropriate null position to insert the new node.

Deletion

Deleting a node from a BST involves three cases:

• Leaf Node: Simply remove the node.
• Node with One Child: Remove the node and replace it with its child.
• Node with Two Children: Find the in-order successor (smallest value in the right subtree) or in-order predecessor (largest value in the left subtree), replace the node's value with the successor/predecessor value, and delete the successor/predecessor.

Searching

To search for a value in a BST:

1. Start from the root.
2. Compare the target value with the current node's value.
3. Move to the left child if the target value is less.
4. Move to the right child if the target value is greater.
5. Repeat steps 2-4 until you find the target value or reach a null node.

Tree Traversal Techniques

In-order Traversal

In in-order traversal, nodes are visited in the following order: left subtree, root, right subtree. This results in visiting nodes in ascending order for BSTs.

Pre-order Traversal

In pre-order traversal, nodes are visited in the following order: root, left subtree, right subtree. This is useful for creating a copy of the tree.

Post-order Traversal

In post-order traversal, nodes are visited in the following order: left subtree, right subtree, root. This is useful for deleting nodes in a tree.

Level-order Traversal

In level-order traversal, nodes are visited level by level from top to bottom and left to right. This can be achieved using a queue.

Watch our couse on Youtube

1. Leetcode 700. Search in a Binary Search Tree
2. Leetcode 653. Two Sum IV - Input is a BST
3. BST Code Optimizations & Approaches (Recursive, Iterative, BFS, DFS)

Advanced Topics

AVL Trees

AVL Trees are a type of self-balancing binary search tree where the difference between heights of left and right subtrees (balance factor) is at most 1. This ensures O(log n) time complexity for insertion, deletion, and search operations.

Red-Black Trees

Red-Black Trees are another type of self-balancing binary search tree with additional properties to ensure balanced height. They have a balance factor that ensures O(log n) time complexity for insertion, deletion, and search operations.

FAQs