Lowest common ancestor of two nodes in a binary tree
Coding problemMediumAsked in: Amazon, American Express, Flipkart, Google, Microsoft, PayPal
Given the root of a binary tree with distinct values, and two values first and second that are both in the tree, return the value of their lowest common ancestor: the deepest node that has both nodes in its subtree.
A node counts as part of its own subtree, so if one node is an ancestor of the other, it is the answer. The two values may be equal. Trees are written in level order, with null for a missing child.
Examples
Example 1
Input: root = [3,5,1,6,2,0,8,null,null,7,4], first = 5, second = 1
Output: 3
Example 2
Input: root = [3,5,1,6,2,0,8,null,null,7,4], first = 5, second = 4
Output: 5
4 is in the subtree of 5, so 5 itself is the answer.
Example 3
Input: root = [1,2], first = 1, second = 2
Output: 1
Constraints
- The tree has between 1 and 100,000 nodes with distinct 32-bit values
- first and second are both values in the tree
Run checks the 3 examples. Submit also runs the hidden tests: edge cases, large inputs and a time limit.
Run your code to see the results here. Ctrl or Cmd + Enter runs; add Shift to submit.