Saturday, February 8, 2014

LCA of two given tree nodes


Solution:
There’s only three cases i need to consider.
  1. Both nodes are to the left of the tree.
  2. Both nodes are to the right of the tree.
  3. One node is on the left while the other is on the right.

static Node lcaOfTwoNodes(Node root, Node x, Node y)
{
if(root == null || x == null || y == null ) return null;

if (root.data >= x.data && root.data <= y.data)
{
return root;
}

if(root.data > y.data)
{
Node result = lcaOfTwoNodes(root.left, x, y);
if(result != null)
{
return result;
}
}else{
return lcaOfTwoNodes(root.right, x, y);
}
return null;
}

No comments:

Post a Comment