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 Tree (Not Binary Search Tree).

Objec­tive: - Find the Low­est Com­mon Ances­tor of two given nodes in a Binary 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 Search Tree.

Exam­ple:

Lowest-Common-Ancestor-Example

Lowest-Common-Ancestor-Example

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

Appraoch:

  1. Start will the root.
  2. If root matches with any of the given nodes (n1, n2) then return root as LCA.
  3. IF not then make recur­sive callas to left sub­tree and right sub­tree for the search of the nodes n1 and n2.
  4. Now both the nodes (n1 and n2) will be in the left sub­tree of the cur­rent vis­it­ing node OR it will be in the right sub­tree of cur­rent vis­it­ing OR n1 and n2 will be in each side of cur­rent vis­it­ing node.
  5. If you find a node which has one node in its left sub­tree and one node in its right sub­tree than this node will be our low­est com­mon ancestor.
  6. If both the nodes (n1 and n2) will be in the left sub­tree of the cur­rent vis­it­ing node then go left
  7. If both the nodes (n1 and n2) will be in the right sub­tree of the cur­rent vis­it­ing node then go right.
  8. See Pic­ture for bet­ter explanation
LCA-in-Binary-Tree

LCA-in-Binary-Tree

Com­plete Code:


Out­put:

Lowest Common Ancestor (8, 30 ) is 2
Lowest Common Ancestor (30, 5 ) is 5

You may also like...

  • Subha Velayutham

    This code does not work when one of the nodes (n1 or n2) does not exist in the tree.