If McDonalds were run like a software company, one out of every hundred Big Macs would give you food poisoning, and the response would be, ‘We’re sorry, here’s a coupon for two more.’ “ Mark Minasi

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.