Search a BST
Compare with root and step left or right, discarding half the remaining nodes each time. About 8 minutes.
Stepping left or right
At any node, compare your target with the node's value. If they are equal, you found it. If the target is smaller, search the left subtree. Otherwise, search the right subtree.
If you fall off the tree by reaching an empty spot, the value is not in the tree. Like following signs in a building: each sign sends you one way, until you arrive or hit a dead end.
if not root or root.val == val:
return root
if val < root.val:
return search_bst(root.left, val)
return search_bst(root.right, val)7 < 8, so 7 can only be on the left. The whole right side is ruled out without looking at it.
Time complexity
Each step moves down one level of the tree. If the tree is balanced, with height about log₂ of n, searching takes only about log n steps rather than n.
That is the same speed-up as halving a sorted list: a tree of a million nodes needs only about 20 steps to find anything.
In a BST with root 50, you search for 35. Which subtree do you explore?
- AThe left subtree
- BThe right subtree
- CBoth subtrees
Show the answer
The left subtree. 35 < 50, so by the BST rule, 35 can only exist in the left subtree.
Search a BST
Given the root of a binary search tree (BST) and an integer val, find the node in the BST whose value equals val and return the subtree rooted with that node. If such a node does not exist, return null.
root = [4, 2, 7, 1, 3], val = 2 → [2, 1, 3]
0 ≤ number of nodes ≤ 10,000 · -1,000,000 ≤ node.val, val ≤ 1,000,000 · All node values are unique