Lowest Common Ancestor of a Binary Search TreeMedium

Lowest Common Ancestor of a Binary Search Tree

Medium 8.7k64% acceptance

TreeDepth-First SearchBinary Search TreeBinary Tree

Given the root of a binary search tree and two values p and q that are present in the tree, return the value of their lowest common ancestor (LCA).

The LCA of p and q is the deepest node that has both of them as descendants (a node is allowed to be a descendant of itself). Note that p and q are passed as plain node values, and you must return the value of the LCA node (not the node object).

The tree is given in level-order (TreeNode with { val, left, right }, null for a missing child).

Example 1

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8

Output: 6

2 and 8 sit on opposite sides of 6, so 6 is their lowest common ancestor.

Example 2

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4

Output: 2

4 lives in the subtree of 2, so 2 (an ancestor of itself) is the LCA.

Example 3

Input: root = [2,1], p = 2, q = 1

Output: 2

Constraints

The number of nodes is in the range [2, 10⁵].
Both `p` and `q` exist in the tree and `p ≠ q`.
-10⁹ ≤ Node.val ≤ 10⁹

Asked atAmazonMicrosoftMetaLinkedIn

JavaScript

⌘↵ to run

Loading editor…

Case 1

[6,2,8,0,4,7,9,null,null,3,5], 2, 8

expected: 6

Case 2

[6,2,8,0,4,7,9,null,null,3,5], 2, 4

expected: 2

Case 3

[2,1], 2, 1

expected: 2

Case 4

[6,2,8,0,4,7,9,null,null,3,5], 3, 5

expected: 4

Case 5

[6,2,8,0,4,7,9,null,null,3,5], 0, 5

expected: 2

Case 6

[5,3,8,1,4,7,9], 7, 9

expected: 8