DSA interview question

Search in a Binary Search Tree

Easy · Algorithms · Topics: bst, recursion

The problem

A dictionary app stores words in a BST keyed by an integer ID, and a lookup must return the node with the given key, along with its subtree, or nothing if the key is absent. The BST property turns this into a single downward walk: compare the key with the current node, and go left if smaller, right if larger, stopping at a match or a null. That's O(h) instead of O(n).

Example: tree [4, 2, 7, 1, 3], key 2 → the subtree [2, 1, 3].

Function signature

TreeNode* searchBST(TreeNode* root, int val);  // the node with val, or nullptr

Test cases

Input `(tree, key)`	Output (subtree, level order)	Explanation
`([4, 2, 7, 1, 3], 2)`	`[2, 1, 3]`
`([4, 2, 7, 1, 3], 5)`	`[]`	Not present
`([4, 2, 7, 1, 3], 7)`	`[7]`	A leaf
`([1], 1)`	`[1]`
`([], 3)`	`[]`	Empty tree

(Confirm: the tree is a valid BST with distinct keys.)

How interviewers phrase it

"Given the root of a BST and an integer val, find the node whose value equals val and return the subtree rooted at it" (LeetCode 700).

Clarifying questions to ask

Distinct keys? (Yes.)
What should be returned if the key is missing? (null.)
Recursive or iterative? (Iterative avoids stack use.)

Follow-ups to expect

"Why can you discard a whole subtree at each step?"
"What's the worst case?"
"Recursive version?"
"How does this generalise?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview