Binary Search Trees (BST)

A Binary Search Tree (BST) is a special type of binary tree that satisfies the following properties:

The left subtree of a node contains only nodes with keys lesser than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
The left and right subtree each must also be a binary search tree.
There must be no duplicate nodes.

These properties allow for efficient searching, insertion, and deletion operations.

Interactive BST Search Visualization

The visualization below demonstrates the search process in a Binary Search Tree. You can search for a value to see how the algorithm traverses the tree to find it.

Binary Search Tree - Search Operation

Current Node

Found

Unvisited

←Go Left (Less)

→Go Right (Greater)

✓Found (Equal)

BST Search Algorithm

1. Start at root node

2. Compare target with current node value

3. If equal → Found! If less → go left, if greater → go right

4. Repeat until found or reach null node

Time Complexity: O(log n) average, O(n) worst case

Binary Search Tree Search Algorithm

Searching in a Binary Search Tree (BST) is highly efficient due to its ordered nature. The key property of a BST is that for any given node, all values in its left subtree are smaller, and all values in its right subtree are larger.

Algorithm Steps

Start at the root of the tree.
Compare the target value with the current node's value.
If the target is equal to the current node's value, the node is found.
If the target is less than the current node's value, move to the left child.
If the target is greater than the current node's value, move to the right child.
Repeat the process until the node is found or you reach a null leaf, which means the value is not in the tree.

BST Search


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        current = root
        while current:
            if val < current.val:
                current = current.left
            elif val > current.val:
                current = current.right
            else:
                return current
        return None