JuniorCodeVery commonNot answered yet
Recursive value search in a binary search tree
Given the root of a binary search tree, return the node holding target, or nullptr if it is not present. Use the BST ordering to prune.
Requirements:
less than the node value → go left; otherwise go right.
- Recursive: empty subtree →
nullptr; equal → return the node;target - O(h) time, where h is the tree height (O(log n) when balanced).
- Check for
nullptrbefore dereferencing a node.
struct TreeNode {
int val;
TreeNode* left = nullptr;
TreeNode* right = nullptr;
};
TreeNode* search(TreeNode* root, int target) {
// your code here
}Write the implementation.
In a BST a node's left subtree holds smaller values and the right subtree larger values. Recursively: empty → nullptr; equal → return; target less → go left; otherwise go right. Time O(h): O(log n) when balanced, O(n) worst case.
- ✗Not checking for nullptr before accessing node->val
- ✗Using a general tree search (visit every node) instead of BST property to prune branches
- ✗Forgetting that BST guarantees are on values, not structural balance
- →How do you insert and delete a node in a BST?
- →What is an AVL tree or a Red-Black tree and why do they guarantee O(log n)?
Contents
Task
Write a recursive function to search for a value in a binary search tree.
Solution
TreeNode* search(TreeNode* root, int target) {
if (!root || root->val == target) return root;
return (target < root->val) ? search(root->left, target)
: search(root->right, target);
}Key points
- BST eliminates half the tree on each step using the ordering property.
- Prefer iterative for large trees to avoid stack overflow.
- O(h): O(log n) balanced, O(n) worst case (degenerate tree).
Contents
