Least common ancestor of 2 nodes in a binary search tree:
Approach:
The main idea of the solution is — While traversing Binary Search Tree from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 < n < n2 is the Lowest or Least Common Ancestor(LCA) of n1 and n2 (where n1 < n2).
So just traverse the BST in pre-order, if you find a node with value in between n1 and n2 then n is the LCA,
if it's value is greater than both n1 and n2 then our LCA lies on left side of the node,
if it's value is smaller than both n1 and n2 then LCA lies on right side.
Approach:
The main idea of the solution is — While traversing Binary Search Tree from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 < n < n2 is the Lowest or Least Common Ancestor(LCA) of n1 and n2 (where n1 < n2).
So just traverse the BST in pre-order, if you find a node with value in between n1 and n2 then n is the LCA,
if it's value is greater than both n1 and n2 then our LCA lies on left side of the node,
if it's value is smaller than both n1 and n2 then LCA lies on right side.
No comments:
Post a Comment