The problem
Given a binary tree and two values p and q that are in it, return the value of their lowest common ancestor: the deepest node that has both in its subtree. A node counts as its own ancestor. All values are different.
tree [3, 5, 1, 6, 2, 0, 8, None, None, 7, 4]
lca(root, 5, 1) -> 3
lca(root, 7, 4) -> 2
lca(root, 5, 4) -> 5
This is any binary tree, not always a search tree, so you cannot steer by comparing values.
The tests write a tree as a level-order list: the values level by level, left to right, with None where a child is missing. So [3, 9, 20, None, None, 15, 7] is 3 with children 9 and 20, where 20 has children 15 and 7. An empty tree is None.
Limits
- Up to 100,000 nodes, at most 300 levels deep.
Builds on TREE-6 Lowest common ancestor.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | Split below the root | Not run | |
| 2 | Far apart | Not run | |
| 3 | One is above the other | Not run | |
| 4 | The same node | Not run | |
| 5 | Not a search tree | Not run | |
| 6 | Deep in one side | Not run | |
| 7 | Ancestor, not sorted | Not run | |
| 8 | 100,000 nodes | Not run |