On this page

Search in a Binary Search Tree

You are given the root of a binary search tree and an integer val. Find the node whose value equals val and return the subtree rooted at that node. If there is no such node, return null.

Constraints:

  • The number of nodes is in the range [1, 5000].
  • 1 <= Node.val <= 10^7, the root is a valid BST, and 1 <= val <= 10^7.

Intuition

1 8
2 / \
3 4 12
4 / \ / \
5 2 6 10 14

Recall the BST property: for every node, everything in the left subtree is smaller and everything in the right subtree is larger. Because of it, one comparison at a node tells us which half of the tree to ignore.

Searching for 6: at 8, 6 is smaller, so go left. At 4, 6 is larger, so go right. At 6, found. We never look at the other half, exactly like binary search on a sorted array.

Approach: Walk Down One Path

  1. Start at the root.
  2. While the node exists and its value is not val:
    • If val is smaller, move to the left child.
    • Otherwise move to the right child.
  3. Return the node. It is either the match or null.

No recursion or extra memory is needed. A plain loop is enough because we follow a single root-to-leaf path.

Code

class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
while (root != nullptr && root->val != val) {
root = val < root->val ? root->left : root->right;
}
return root;
}
};

Complexity

Time: O(h)

We follow one root-to-leaf path. That is O(log n) for a balanced BST and O(n) for a skewed one.

Space: O(1)

The iterative loop uses no extra memory. A recursive version would use O(h) stack.

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"In a BST, everything on the left is smaller and everything on the right is larger, so a single comparison tells me which half to discard. I start at the root and loop: if the value I want is smaller than the current node I go left, otherwise I go right, until I find the value or run out of nodes. I return the node I stop at, which is either the match or null. It follows a single path, so time is O of h, which is log n for a balanced tree, and space is O of one because it is iterative."
Next TopicCeil in a Binary Search Tree