DiffPush Tier Binary Trees · Hard O(n) · O(h)
An HR system stores reporting lines as a binary tree and must settle which manager is the closest common supervisor of two employees. Company policy allows an employee to supervise themselves in this lookup, so if one of the pair reports up through the other, the deeper one's chain wins at their meeting point. The system returns that junction's id for every dispute.
Input: A binary tree as a level-order array (null marks a missing child) plus two integers p and q — the values of the two nodes. Node values are unique.
Output: Return the value of the lowest common ancestor of p and q.
1 <= number of nodes <= 10^5-10^4 <= node value <= 10^4Both p and q exist in the treeInput: {"tree":[3,5,1,6,2,0,8,null,null,7,4],"p":5,"q":1}
Output: 3
5 sits in the left wing and 1 in the right, so the root 3 is their meeting point.
Input: {"tree":[3,5,1,6,2,0,8,null,null,7,4],"p":5,"q":4}
Output: 5
4 descends from 5, and a node counts as its own ancestor.