How do you solve Search in a Binary Search Tree?

Iteratively traverse the tree starting from the root. At each node, compare val with the node's value. If equal, return the node. If val is less, move to the left child; if greater, move to the right child. If the traversal reaches a null node, return null indicating val is not present.

What pattern does Search in a Binary Search Tree use?

The Pattern: DFS (Directed Search in BST) The Heuristic: Use the BST ordering property to prune the search space at each step by moving only to the subtree that could contain the target, effectively performing a binary search on the tree.

Search in a Binary Search Tree | DFS

Q: What is the time complexity of Search in a Binary Search Tree?

O(h). Each step moves down one level of the tree, and the maximum number of steps is the height h of the BST. In a balanced BST, h = O(log n), making the search efficient.

Problem

Given the root of a binary search tree and an integer val, return the subtree rooted with the node whose value equals val. If such a node does not exist, return null.

The number of nodes in the tree is in the range [1, 5000]
1 ≤ Node.val ≤ 10⁷
root is a valid binary search tree
1 ≤ val ≤ 10⁷

Example

Input: root = [4,2,7,1,3], val = 2

Output: [2,1,3]

Starting at the root (4), the algorithm compares val (2) with current node's value. Since 2 < 4, it moves to the left child (2). It finds a node with value 2, which matches val, so it returns the subtree rooted at this node, which includes its children 1 and 3.

Approach

Straightforward Solution

A brute-force approach would traverse the entire tree (e.g., DFS or BFS) to find the node with value val, resulting in O(n) time complexity where n is the number of nodes.

Core Observation

The BST property allows pruning the search space at each node: if val is less than the current node's value, the target must be in the left subtree; if greater, in the right subtree; if equal, the current node is the answer.

Path to Optimal

Leveraging the BST property, the search can be directed at each step to only one subtree, reducing the search space drastically. This transforms the problem into a binary search on the tree structure, achieving O(h) time complexity where h is the tree height.

Optimal Approach

Preview

Iteratively traverse the tree starting from the root. At each node, compare val with the node's value…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(h)

Each step moves down one level of the tree, and the maximum number of steps is the height h of the BST. In a balanced BST, h = O(log n), making the search efficient.

Space

O(1)

The iterative approach uses only a constant amount of extra space for the current pointer and variables, excluding the input tree structure.

Solution

Python

1class Solution:
  def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
      current = root
4
      while current:
          if current.val == val:
              return current
8
          if val < current.val:
              current = current.left
          else:
              current = current.right
13
      return None

Step-by-Step Solution

1

Traverse the BST Iteratively Using Directed Comparisons

3current = root
5while current:
6    if current.val == val:
7        return current
9    if val < current.val:
10        current = current.left
11    else:
12        current = current.right
14return None

Objective

To navigate the BST from the root towards the target node by comparing val with the current node's value and moving left or right accordingly.

Key Insight

By comparing val with the current node's value, the algorithm exploits the BST ordering to decide the unique subtree to explore next. This directed traversal avoids unnecessary exploration of irrelevant subtrees, ensuring efficient search. The iterative approach maintains a pointer that moves down the tree until the target is found or the search space is exhausted.

Interview Quick-Check

Core Logic

At each node, compare val with node.val to decide whether to move left, right, or return the current node if equal.

State & Boundaries

The loop continues while the current node is not null, ensuring all possible nodes on the search path are checked.

Common Pitfalls & Bugs

Failing to update the current pointer correctly when val < or > node.val can cause infinite loops or incorrect results.

Complexity

This approach guarantees O(h) time complexity, where h is the height of the BST, by pruning half the search space at each step.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 6 Critical

if current.val == val:

Check if the current node's value matches the target val.

This equality check identifies the successful search termination condition, allowing immediate return of the matching subtree.

Line 9 Critical

if val < current.val:

Compare val with the current node's value to decide traversal direction.

This comparison leverages the BST property to prune the search space, ensuring only the relevant subtree is explored next.

Line 14 Critical

return None

Return None if the search reaches a null node without finding val.

Returning None correctly signals that the target value does not exist in the BST after exhaustive directed search.

Full line-by-line criticality + rationale for all 9 lines available on Pro.

Test Your Understanding

Why does the BST property allow us to avoid searching both subtrees at each node?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Search in a Binary Search Tree from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Search in a Binary Search Tree drill

or drill a free problem

1	`class Solution:`
2	`def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:`
3	`current = root`
4
5	`while current:`
6	`if current.val == val:`
7	`return current`
8
9	`if val < current.val:`
10	`current = current.left`
11	`else:`
12	`current = current.right`
13
14	`return None`

3	`current = root`
5	`while current:`
6	`if current.val == val:`
7	`return current`
9	`if val < current.val:`
10	`current = current.left`
11	`else:`
12	`current = current.right`
14	`return None`