LCA of two tree nodes

Given two nodes in a binary tree. Find their lowest common ancestor.

Ex:

                                      5
                                  9        11
                               2     3   7
                                   1      

LCA(1, 2) = 9

Solution: Recursive traversal

Base Case:

current node == null; return null

current node == node1 || node 2; return current

Recursive Rule:

1. Initialize two new nodes, left and right

2. if both not null, found, return

3. if one found, return it up

4. if both null, return null

Implementation:

public TreeNode findLCA(TreeNode one, TreeNode two){
    //sanity check
    if ( one == null || two == null )return null;
    TreeNode root = one;
    while ( root.parent != null ){
        root = root.parent;
    }
    TreeNode result = LCAhelper(root, one, two)
    return result;
}   

public TreeNode LCAhelper(TreeNode root, TreeNode one, TreeNode two){
    if ( root == null ) return null;
    if ( root == one || root == two) return root;
    
    TreeNode leftCheck = LCAhelper(root.left, one, two);
    TreeNode rightCheck = LCAhelper(root.right, one, two);
    
    //return non null node up tree
    if (leftCheck == null) return rightCheck;
    if (rightCheck == null) return leftCheck;
    
    return root;
} 

Time complexity: Every node traveled O(N)

Space complexity: No additional struct used O(1) Call stack worst case O(h)