Programming is like sex: one mistake and you’re providing support for a lifetime. Michael Sinz

Lowest Common Ancestor

Language Java | Level Intermediate | Category Data structure | September 6, 2015 7:58 am

Data structure Description

Write a program to find the least common ancestor from given a binary tree and two values say n1 and n2.

According to the definition of LCA on Wikipedia, “Lowest common ancestor (LCA) of two nodes v and w in a tree or directed acyclic graph (DAG) is the lowest (i.e. deepest) node that has both v and w as descendants, where we define each node to be a descendant of itself”



All Binary Tree Values: 6  2  5  1  9  4  7  11  3  
Lowest Common Ancestor of Node 3 and 9 is: 4
Lowest Common Ancestor of Node 3 and null is: 3
Lowest Common Ancestor of Node 11 and null is: 11



No comments available!

Please login to add comments.