Lowest Common Ancestor

Problem Description
level: medium

Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.
The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.

For the following binary tree:

LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7

1. tradition method
2. divide & conquer algorithm

Approach 1:
Put the parent of the nodes into the two lists, then scan the lists from the bottom, to find the lower common one

For example: LCA(5,6)
List 1: 5,7,4
List 2: 6,7,4

comparing the lists from bottom, 4, 7 are common parents, and 7 is the closest

Another example: LCA(3, 5)
list 1: 3,4
list 2: 5,7,4
comparing the lists from bottom, 4 is common parent, and the closest

Approach 2:

Divide & conquer

psuedo code:

Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedInShare on RedditShare on StumbleUponEmail this to someoneShare on TumblrDigg this

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">