Trees - Lowest Common Ancestor of a BST

Given a BST, find the lowest common ancestor (LCA) of two given nodes p and q. LCA is defined as the lowest node that has both p and q as descendants.

Input: root=[6,2,8,0,4,7,9], p=2, q=8 → Output: 6

Input: root=[6,2,8,0,4,7,9], p=2, q=4 → Output: 2

Exploit BST property: if both p and q are less than root, LCA is in left subtree. If both greater, in right subtree. Otherwise, root is the LCA.

While root != null:
If both p.val < root.val and q.val < root.val: go left.
Else if both > root.val: go right.
Else: return root (it is the split point).

class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { while (root != null) { if (p.val < root.val && q.val < root.val) root = root.left; else if (p.val > root.val && q.val > root.val) root = root.right; else return root; } return null; } }

Time Complexity: O(H)
Space Complexity: O(1)