Skip to content
BASA DSA

Lowest Common Ancestor of a Binary Search Tree

MediumTrees

In a binary search tree with distinct values, return the existing node that is the lowest common ancestor of p and q. A node is its own ancestor. The encoded p and q values identify actual nodes in root; returning a new node is invalid.

Example 1

Argument 1 tree: level-order input; omitted children are null.Argument 1 tree: level-order input; omitted children are null. Vertices: node 0: 6, node 1: 2, node 2: 8, node 3: 0, node 4: 4, node 5: 7, node 6: 9, node 7: 3, node 8: 5. Edges: node 0 (6) — node 1 (2) left child; node 0 (6) — node 2 (8) right child; node 1 (2) — node 3 (0) left child; node 1 (2) — node 4 (4) right child; node 2 (8) — node 5 (7) left child; node 2 (8) — node 6 (9) right child; node 4 (4) — node 7 (3) left child; node 4 (4) — node 8 (5) right child.628047935
Argument 1 tree: level-order input; omitted children are null.

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

Explanation

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

Example 2

Argument 1 tree: level-order input; omitted children are null.Argument 1 tree: level-order input; omitted children are null. Vertices: node 0: 6, node 1: 2, node 2: 8, node 3: 0, node 4: 4, node 5: 7, node 6: 9, node 7: 3, node 8: 5. Edges: node 0 (6) — node 1 (2) left child; node 0 (6) — node 2 (8) right child; node 1 (2) — node 3 (0) left child; node 1 (2) — node 4 (4) right child; node 2 (8) — node 5 (7) left child; node 2 (8) — node 6 (9) right child; node 4 (4) — node 7 (3) left child; node 4 (4) — node 8 (5) right child.628047935
Argument 1 tree: level-order input; omitted children are null.

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

Explanation

2 is an ancestor of 5 and qualifies as its own ancestor.

Example 3

Argument 1 tree: level-order input; omitted children are null.Argument 1 tree: level-order input; omitted children are null. Vertices: node 0: 2, node 1: 1. Edges: node 0 (2) — node 1 (1) left child.21
Argument 1 tree: level-order input; omitted children are null.

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

Explanation

Root 2 is one queried node and the other's parent, so return that existing root.

Constraints

  • 2 <= number of nodes <= 10000
  • p and q exist and have distinct values
  • Tree is a strict BST

Function contractlowestCommonAncestorArguments: tree, treeNode, treeNode
Loading draft…
SolutionRuns on your device