Java Code that finds Least Common Ancestor in a binary tree

This problem is broken down into 3 pieces.

1. Find the paths to the target nodes.
2. Push them in a stack.
3. Reverse the stacks to find the element just before a mismatch.

Crux is this:

========================================================================

public static Node leastCommonAncestor(Node root, Node one, Node two)

{

if( one == null ) return two;

if( two == null ) return one;

Stack s1 = new Stack();

Stack s2 = new Stack();

s1.push(root);

s2.push(root);

boolean oneFound = findPath(root, one, s1);

boolean twoFound = findPath(root, two, s2);

if( ! oneFound || ! twoFound ) return null;

Stack rev1 = reverseStack(s1);

Stack rev2 = reverseStack(s2);

Node first = (Node) rev1.pop();

Node second = (Node) rev2.pop();

Node lca = first;

while( first.value == second.value )

{

lca = first;

if( ! rev1.empty() ) 

{

first = (Node) rev1.pop();

}

if( ! rev2.empty() )

{

second = (Node) rev2.pop();

}

}

return lca;

}

========================================================================

Code that reverses the stack should be easy. But findPath is the one needs attention.

========================================================================

public static boolean findPath(Node current, Node destNode, Stack s)

{

if( current == null ) return false;

if( current.value == destNode.value )

{

return true;

}

if( current.left != null )

{

s.push(current.left);

boolean found = findPath(current.left, destNode, s);

if(  found ) return true;

else s.pop();

}

if( current.right != null )

{

s.push(current.right);

boolean found = findPath(current.right, destNode, s);

if(  found ) return true;

else s.pop();

}

return false;

}

========================================================================

Test execute it here.