Searching in a Binary Search Tree

What Is Searching in a Binary Search Tree?

Binary Search Tree search is the process of finding whether a specific value exists in a Binary Search Tree (BST). The search operation takes advantage of the ordering property of the tree instead of checking every node.

At each node, the target value is compared with the current value. If the target is smaller, the search continues in the left subtree. If the target is greater, it continues in the right subtree. If both values are equal, the target has been found.

How BST Search Works

Consider the following Binary Search Tree:

        50
       /  \
     30    70
    /  \  /  \
  20   40 60   80

Suppose we want to search for 60.

1. Start at 50.
2. 60 is greater than 50, so move to the right subtree.
3. Reach 70.
4. 60 is smaller than 70, so move to the left subtree.
5. Reach 60 and the value is found.

Only the nodes 50, 70, and 60 needed to be examined. The other branches could be ignored.

The BST Ordering Rule

Searching works efficiently because every node divides the remaining search space into smaller and larger values.

• If target < current.value, search the left subtree.
• If target > current.value, search the right subtree.
• If target === current.value, the target has been found.

This decision process is repeated until the value is found or the search reaches an empty subtree.

Iterative BST Search

An iterative implementation uses a loop to move through the tree. It does not create recursive function calls, making the control flow straightforward.

function search(root, target) {
  let current = root;

  while (current !== null) {
    if (target === current.value) {
      return current;
    }

    if (target < current.value) {
      current = current.left;
    } else {
      current = current.right;
    }
  }

  return null;
}

The function returns the matching node when the value is found. If the traversal reaches null, the target does not exist in the tree.

Searching for an Existing Value

The following example searches for 40 in a BST:

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function search(root, target) {
  let current = root;

  while (current !== null) {
    if (target === current.value) {
      return current;
    }

    if (target < current.value) {
      current = current.left;
    } else {
      current = current.right;
    }
  }

  return null;
}

const root = new Node(50);
root.left = new Node(30);
root.right = new Node(70);
root.left.left = new Node(20);
root.left.right = new Node(40);

const result = search(root, 40);

console.log(result ? result.value : 'Not found');

Searching for a Missing Value

If the target value does not exist, the search continues until it reaches a null reference. At that point, there is no subtree in which the value could exist.

const result = search(root, 45);

if (result === null) {
  console.log('Value not found');
}

For a valid BST, reaching a null child means the target is not present along that search path.

Recursive BST Search

BST search can also be implemented recursively. Each recursive call searches one of the two subtrees based on the comparison with the current node.

function search(root, target) {
  if (root === null || root.value === target) {
    return root;
  }

  if (target < root.value) {
    return search(root.left, target);
  }

  return search(root.right, target);
}

The base case handles both situations where the value has been found and where the search has reached an empty subtree.

Iterative vs Recursive Search

Both approaches use the same BST ordering rule. The main difference is how the traversal state is maintained.

Searching Step by Step

Consider searching for 65 in this tree:

        50
       /  \
     30    70
          /  \
        60    80
          \
           65

The search follows this path:

1. Start at 50. Since 65 is greater, move right.
2. At 70, since 65 is smaller, move left.
3. At 60, since 65 is greater, move right.
4. At 65, the target matches the current value.

Search path:

50 → 70 → 60 → 65

BST Search and Tree Height

The number of comparisons required by a BST search depends on the height of the tree. A shorter tree generally requires fewer comparisons, while a skewed tree can require many.

For example, a balanced tree may allow a search to eliminate approximately half of the remaining structure at each level. A completely skewed tree can behave more like a linear sequence.

Search Complexity

BST search has a time complexity based on the tree height. If the tree height is h, the search takes O(h) time.

The auxiliary space of iterative search is O(1). Recursive search uses O(h) call-stack space, where h is the height of the tree.

Searching with Duplicate Values

Duplicate values require an explicit policy. A BST implementation may reject duplicates, store them consistently in one direction, or maintain a count at each node.

If duplicates are stored in the right subtree, for example, the insertion and search logic must consistently follow that rule.

        50
       /  \
     30    50
             \
              70

When searching for 50, the first matching node is normally returned. If an application needs every occurrence, the search algorithm must continue after finding a match.

Finding the Minimum and Maximum

BST ordering also makes it easy to find the minimum and maximum values. The minimum value is located at the leftmost node, while the maximum value is located at the rightmost node.

function findMin(root) {
  if (root === null) {
    return null;
  }

  let current = root;

  while (current.left !== null) {
    current = current.left;
  }

  return current;
}

function findMax(root) {
  if (root === null) {
    return null;
  }

  let current = root;

  while (current.right !== null) {
    current = current.right;
  }

  return current;
}

Searching for a Range of Values

A BST can also be used to find values within a range. The ordering property allows branches that cannot contain values in the requested range to be skipped.

function searchRange(root, low, high, result = []) {
  if (root === null) {
    return result;
  }

  if (root.value > low) {
    searchRange(root.left, low, high, result);
  }

  if (root.value >= low && root.value <= high) {
    result.push(root.value);
  }

  if (root.value < high) {
    searchRange(root.right, low, high, result);
  }

  return result;
}

This approach avoids traversing subtrees that are guaranteed to contain values outside the requested range.

BST Search vs Linear Search

A linear search examines elements sequentially. A BST search uses the ordering of the tree to eliminate branches that cannot contain the target.

Common BST Search Mistakes

• Searching both subtrees instead of using the BST ordering property.
• Moving left when the target is greater than the current node.
• Moving right when the target is smaller than the current node.
• Forgetting to handle an empty tree.
• Returning the wrong result when the target is missing.
• Assuming every BST search is O(log n) regardless of tree shape.
• Ignoring the duplicate-value policy used by the BST implementation.
• Using recursive search without considering the height of a highly skewed tree.

When to Use BST Search

BST search is useful when values are maintained in an ordered tree and the application needs repeated lookup operations along with dynamic insertion and deletion.

For applications that require guaranteed logarithmic performance, self-balancing trees such as AVL Trees or Red-Black Trees can be used instead of a plain BST.

Key Takeaways

• BST search uses the ordering property of the tree.
• Smaller targets are searched in the left subtree.
• Greater targets are searched in the right subtree.
• An equal value means the target has been found.
• Search takes O(h), where h is the tree height.
• A balanced BST provides O(log n) search.
• A skewed BST can degrade to O(n) search.
• Iterative search uses O(1) auxiliary space.
• Recursive search uses O(h) call-stack space.