Maintained by Vikas Dulgunde, software engineer
You receive a binary search tree encoded as a level-order array, the same layout used on most judges, where null marks a slot with no node. Two values p and q are also given, and both are guaranteed to exist as nodes in the tree.
The lowest common ancestor of p and q is the node furthest from the root that still has both p and q in its subtree. A node is considered part of its own subtree, so if one of the two values sits directly above the other on the path from the root, that higher value is the answer.
Return the value stored at that ancestor node, not the node object itself. Because every value in a BST is unique, there is exactly one correct answer.
The structure being a BST is the part worth exploiting: at any node you can tell which side each target falls on purely by comparing values, which means you never have to search blindly.
2 lives in the left subtree of the root and 8 lives in the right subtree, so the two paths split at the root 6. No node deeper than 6 holds both, making 6 the answer.
4 is a descendant of 2 (2 has children 0 and 4). Since a node is its own descendant, 2 contains both targets and nothing below 2 does, so 2 is the lowest common ancestor.
Both 3 and 5 hang under node 4 (3 is its left child, 5 its right child). They first share an ancestor at 4, so 4 is returned.
Visible test cases
You do not need to compare the two targets against every node. The BST ordering tells you, at each node, whether a value lives to the left, to the right, or right here.
Walk down from the root. If both p and q are smaller than the current value, the split has not happened yet, so go left. If both are larger, go right.
The first node where p and q do not both fall on the same side (one is smaller and one is larger, or one equals the node) is the lowest common ancestor. Stop and return it.
Treat it like a generic binary tree: find the full path from the root down to p and the full path down to q, then walk both paths together and take the last node they share.
Use the ordering property: at each node, the comparison of p and q against the current value tells you instantly which subtree both belong to, or that the split point has been reached.