Data Structures19 sections · 729 units
Open in Course

Problem - LCA of BST

Easier than general trees

Given a BST and two nodes p and q, find their lowest common ancestor. The LCA is the lowest node that has both p and q as descendants (a node can be a descendant of itself).

Example: In BST [6,2,8,0,4,7,9,null,null,3,5][6,2,8,0,4,7,9,null,null,3,5], LCA of 2 and 8 is 6. LCA of 2 and 4 is 2.

Unlike general binary trees, you can use the BST property to guide your search efficiently. Constraints: all node values are unique, both p and q exist in the tree.