Locate a Key in a Search Tree
EasyTrees
Problem
A warehouse indexes its shelf codes in a binary search tree: for every node, all codes in its left subtree are smaller and all codes in its right subtree are larger. Codes are distinct.
Given the root and a key, return the subtree rooted at the node whose value equals key. If no node holds key, return an empty tree.
Example 1
- Input:
- root = [4, 2, 7, 1, 3], key = 2
- Output:
- [2, 1, 3]
2 < 4, so go left and land on 2; its subtree is 2 with children 1 and 3.
Example 2
- Input:
- root = [4, 2, 7, 1, 3], key = 5
- Output:
- []
5 > 4 leads to 7, 5 < 7 leads to an empty left child: 5 is not stored.
Example 3
- Input:
- root = [8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13], key = 6
- Output:
- [6, 4, 7]
Constraints
- 0 ≤ number of nodes ≤ 10^4
- -10^7 ≤ node.val, key ≤ 10^7
- All values are distinct and the tree is a valid search tree.
Hint
Show the first hint
At any node, can the key be in both subtrees, or does the ordering rule tell you which side to search?
Walkthrough
How to approach it
01Clarify before coding
- What should be returned when the key is missing? An empty tree (null / None).
- Can values repeat? No, codes are distinct, so at most one node matches.
- Should I return a copy? No, returning the existing node is enough: its subtree comes with it.
02Brute force
Traverse the whole tree (DFS or BFS) and return the node whose value equals key.
Cost: O(n) time and O(h) or O(w) space; it ignores the ordering and visits up to 10^4 nodes when a balanced tree needs about 14 comparisons.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.