Home

Step 3 of 6

50% Complete

Search Operation in Binary Search Trees

Learn how to find values in a binary search tree

Understanding the Search Operation

Searching in a binary search tree (BST) involves finding a node with a specific value. The BST property makes this operation efficient because at each step, we can eliminate half of the remaining tree.

Search Algorithm

The search algorithm follows these steps:

  1. Start at the root of the tree.
  2. If the tree is empty, the value is not found.
  3. If the current node's value equals the search value, the search is successful.
  4. If the search value is less than the current node's value, recursively search in the left subtree.
  5. If the search value is greater than the current node's value, recursively search in the right subtree.

Implementation

Here's how we implement the search operation in TypeScript:

class TreeNode {
  value: number;
  left: TreeNode | null;
  right: TreeNode | null;
 
  constructor(value: number) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
 
class BinarySearchTree {
  root: TreeNode | null;
 
  constructor() {
    this.root = null;
  }
 
  // Recursive search
  search(value: number): TreeNode | null {
    return this.searchNode(this.root, value);
  }
 
  private searchNode(node: TreeNode | null, value: number): TreeNode | null {
    // If the tree is empty or we've reached the end of a branch
    if (node === null) {
      return null;
    }
 
    // If the value is found
    if (value === node.value) {
      return node;
    }
 
    // If the value is less than the current node's value, search in the left subtree
    if (value < node.value) {
      return this.searchNode(node.left, value);
    }
    
    // If the value is greater than the current node's value, search in the right subtree
    return this.searchNode(node.right, value);
  }
 
  // Iterative search (alternative implementation)
  searchIterative(value: number): TreeNode | null {
    let current = this.root;
 
    while (current !== null) {
      // If the value is found
      if (value === current.value) {
        return current;
      }
 
      // If the value is less than the current node's value, go to the left subtree
      if (value < current.value) {
        current = current.left;
      } 
      // If the value is greater than the current node's value, go to the right subtree
      else {
        current = current.right;
      }
    }
 
    // Value not found
    return null;
  }
}

Example

Let's consider the following binary search tree:

        10
       /  \
      5    15
     / \  / \
    3   7 12 18

Let's search for the value 7:

  1. Start at the root (10).
  2. 7 < 10, so we move to the left child (5).
  3. 7 > 5, so we move to the right child (7).
  4. 7 === 7, so we've found the value!

Now, let's search for the value 9:

  1. Start at the root (10).
  2. 9 < 10, so we move to the left child (5).
  3. 9 > 5, so we move to the right child (7).
  4. 9 > 7, but there's no right child of 7, so the value is not found.

Time and Space Complexity

Time Complexity: O(h) where h is the height of the tree. In a balanced BST, this is O(log n), but in the worst case (a skewed tree), it can be O(n).

Space Complexity: O(h) for the recursive implementation due to the call stack, where h is the height of the tree. The iterative implementation has O(1) space complexity.