Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Lowest Common Ancestor in a Binary Search Tree.

Objec­tive: - Find the Low­est Com­mon Ances­tor of two given nodes in a Binary Search Tree

What is Low­est Com­mon Ancestor

In a given binary tree, The low­est com­mon ances­tor of two nodes n1 and n2 will be a node X such that node X will be the low­est node who has n1 and n2 as its descendants.

Sim­i­lar Prob­lem: Low­est Com­mon Ances­tor in a Binary Tree ( Not Binary Search Tree).

Exam­ple:

Lowest-Common-Ancestor-BST

Lowest-Common-Ancestor-BST

Input: A binary Search Tree and two nodes n1 and n2.

Appraoch:

  1. Start will the root.
  2. If root>n1 and root>n2 then low­est com­mon ances­tor will be in left subtree.
  3. If root<n1 and root<n2 then low­est com­mon ances­tor will be in right subtree.
  4. If Step 2 and Step 3 is false then we are at the root which is low­est com­mon ances­tor, return it.
LCA-in-Binary-Search-Tree

LCA-in-Binary-Search-Tree

Com­plete Code:


Out­put:

Recursive-Lowest Common Ancestor of Nodes 5 and 14 is : 10
Iterative-Lowest Common Ancestor of Nodes 5 and 14 is : 10

You may also like...