Find min path between two nodes of a binary tree

Given two nodes in a binary tree with parent pointer. Find the min path from between two nodes. Note that root of the tree is not given

Let’s start with an example as follows.

                             1
                          /      \
                         2        3
                      /         /   \
                     4         5     6
                       \           /
                        7         8

1. Use parent pointer to find the level of the two nodes. –> O(height) = O(lgn) for balanced tree and O(n) for unbalanced tree.
2. Now, keep two pointers: one pointing to the deeper node and second pointing to the shallower node. Also keep two lists: one for putting the nodes in the path from first node to the lowest common ancestor. Another for putting nodes in the path from second node to LCA node in reverse order (i.e. always insert in front of the list).
3. Move deeper pointer up (one parent each time) for delta=level-level2 times. Also add nodes to the proper list accordingly. –> O(lgn) for balanced tree and O(n) for unbalanced tree.
4. Now, two pointers are leveled. Move up both pointer at the same time up one parent until the pointers hit to the common parent (lca). While going up we already populate first list by the nodes in the path from first node to lca in forward order; and populated 2nd list by the nodes in the path from second node to lca in reverse order. –> O(lgn) for balanced tree and O(n) for unbalanced tree
5. concat second list with first list and voila! we have our answer. –> O(1)

overall complexity is O(lgn) for balanced tree and O(n) for unbalanced tree.

A simple implementation for the above algorithm is as follows:

public static int getHeight(TreeNode p) {
    int height = 0;
    while (p != null) {
        height++;
        p = p.parent;
    }
    return height;
}

// As root->parent is NULL, we don't need to pass root in.
public static Set<Integer> minPath(TreeNode p, TreeNode q) {
    final int h1 = getHeight(p);
    final int h2 = getHeight(q);
    final LinkedList<Integer> pathDeeper = new LinkedList<Integer>();
    final LinkedList<Integer> pathShallower = new LinkedList<Integer>();
    // swap both nodes in case p is deeper than q.
    if (h1 > h2) {
        swap(h1, h2);
        swap(p, q);
    }
    // invariant: h1 <= h2.
    final int dh = h2 - h1;
    for (int h = 0; h < dh; h++) {
        pathDeeper.addFirst(q.key);
        q = q.parent;
    }
    while (p != null && q != null) {
        pathShallower.addLast(p.key);
        pathDeeper.addFirst(q.key);

        if (p == q) {
            final Set<Integer> path = new HashSet<Integer>();
            path.addAll(pathShallower);
            path.addAll(pathDeeper);
            return path;
        }
        p = p.parent;
        q = q.parent;
    }
    return null; // p and q are not in the same tree
}