Lowest Common Ancestor of a Binary Tree

MediumTreesdfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given the root of a binary tree and the values p and q of two different nodes in it, return the value of their **lowest common ancestor**. The lowest common ancestor is the deepest node that has both p and q among its descendants, where a node counts as a descendant of itself. So if one of the two nodes lies inside the other's subtree, the upper node is the answer. All values in the tree are distinct, and both p and q are guaranteed to be present. The tree is an ordinary binary tree, not a binary search tree.

Examples

Input: root = [10,4,7,1,9,null,3,null,null,8,2], p = 8, q = 1
Output: 4
8 is under 9, which is under 4; 1 is also a child of 4. No deeper node covers both.
Input: root = [10,4,7,1,9,null,3,null,null,8,2], p = 2, q = 7
Output: 10
2 is in the left subtree of the root and 7 is its right child.
Input: root = [10,4,7,1,9,null,3,null,null,8,2], p = 9, q = 2
Output: 9
2 is a child of 9, and a node is its own descendant.

Constraints

  • 2 <= number of nodes <= 10^5
  • -10^9 <= Node.val <= 10^9
  • All values are distinct
  • p != q
  • `p` and `q` are values of nodes in the tree

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More dfs problems