TreeNode(val, left=None, right=None) is in the starter. Keep it.
Implement lowest_common_ancestor(root, p, q) -> TreeNode.
p and q are two distinct nodes that are both in the tree. Return the deepest node that has both of them as descendants. A node counts as its own descendant, so if p is an ancestor of q the answer is p. This is a plain binary tree, not a BST, so the values don't tell you which way to go. Values are distinct.
# 6
# / \
# 2 8
# / \ / \
# 0 4 7 9
# / \
# 3 5
lowest_common_ancestor(root, node3, node0) # node 2
lowest_common_ancestor(root, node2, node5) # node 2 (a node is its own descendant)
lowest_common_ancestor(root, node5, node9) # node 6
Return the node object itself, compared by identity. The tree has up to 10,000 nodes and depth at most 500. Aim for O(n) per call.
Show hint
Let a recursive call report whether it found p or q in its subtree. Think about what it means when a node hears "found" from both of its children.