Standard Bar Binary Search Trees · Practice Problems O(h) · O(h)
A packet router organizes destination addresses in a sorted tree, and two packets must share a staging checkpoint on their way to different addresses. The correct checkpoint is the deepest router where the two destinations still travel together: while both targets sit on the same side of a router, the walk continues into that wing; the moment they split — or one of them IS the router — that router is the meeting point.
Input: A binary search tree as a level-order array (null marks a missing child) plus two integers p and q — the target node values.
Output: Return the value of the lowest common ancestor of p and q. A node counts as an ancestor of itself.
1 <= number of nodes <= 10^5-10^9 <= node value, p, q <= 10^9All node values are unique; both p and q exist in the treeInput: {"tree":[6,2,8,0,4,7,9,null,null,3,5],"p":2,"q":8}
Output: 6
2 and 8 split onto opposite wings of 6, making it the fork point.
Input: {"tree":[6,2,8,0,4,7,9,null,null,3,5],"p":2,"q":4}
Output: 2
4 lives under 2, and a node is its own ancestor.