Looking for fast algorithm to find distance between two nodes in binary tree

How do I find the distance between two nodes in a binary tree? Equivalently, what algorithms are there for finding the most recent common ancestor (lowest common ancestor开发者_JAVA技巧) of two nodes?

1. calculate the list of ancestors for each node
2. find the common prefix
3. the last element from the common prefix is the lowest common ancestor
4. remove the common prefix from both ancestor lists
5. the distance is the sum of lengths of the remaining lists +1

Finding the common ancestor is almost certainly the easier task. This is a pretty simple one: start from the root of the tree, and descend the tree until you reach a node where you would have to descend to different children to get to the two nodes in question. That node is the common parent (assuming the tree contains both nodes, of course).

As everybody here seems to know, if you keep a note of the distance each node is from the root, then once you have found the lowest common ancestor of the two nodes you can work out the distance they are from each other in constant time.

If you do one time work only linear in the size of the tree it turns out that you can then find the lowest common ancestor of any two nodes in constant time (no matter how deep the tree is). See http://en.wikipedia.org/wiki/Lowest_common_ancestor

The Baruch Schieber and Uzi Vishkin algorithm for lowest common ancestor is entirely practical to use and to program.

Make two sets consisting of the ancestors of each: while the union of the sets is empty, add the next ancestor of each node to the appropriate list. Once there is a common node, that's the common ancestor.

First, search for the height of the first element. Also, return the path to get there using a linked list. You can do this in O(logN) time . Assume tree is balanced, where height is logN. let H1 = height of first element.

Then, search for the heigh to the second element. Also, return the path to get there using a linked list. You can do this in O(logN) time. Let H2 = height of second element.

Trace through both linked list collected until the values are no longer equal (paths diverge) The point before they diverge, call the height of that node H3.

Thus, the longest path is H1 + H2 - 2*H3 (since you need H1 to go to H1, and H2 to go to H2. But really, you can trace back from H1 up till H1-H3. and then move to H2 from H3. So it's (H1-H3) + (H2-H3) = H1+H2 -2*H3.

Implementation details should be straight forward

search(Tree* Head, Node* Value, LinkedList path, int distance); 

Thus,

search(Head, Value1, path1, height1); 
search(Head, Value2, path2, height2); 

i = 0; 
while (path1[i] == path2[i])
{
    i++; 
}
height3 = i-1; 
return height1+height2- 2*height3; 

Time Complexity: O(logN)+ O(logN) + O(logN) = O(logN) Space Complexity: O(logN) (to store both linked list of distances)

here is DP implementation for BT distance. Not optimal, but interesting. it creates the tree 1st, with an input array.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created by juanmf on 05/02/17.
 */
public class Main2 {
    /**
     * {50, 60, 30, 10, 20, 40} will form a Node Structure as follows
     * 5
     * ├─L─ 3
     * │   ├─L─ 1
     * │   │   └─R─ 2
     * │   └─R─ 4
     * └─R─ 6
     * L: left
     * R: Right
     * Path should be: [4, 3, 1, 2]
     * steps: 3 <- output
     *
     * @param args
     */
    public static void main(String[] args) {
        int i = pathSteps(new int[] {50, 60, 30, 10, 20, 40}, 6, 20, 60);
        System.out.println(i);
    }

    private static int pathSteps(int[] ints, int n, int from, int to) {
        Node root = null;
        Map<Node, Node> allNodes = new HashMap<>();

        for (int i: ints) {
            if (root == null) {
                root = new Node(i);
                allNodes.put(root, root);
            }
            root.addNode(i, allNodes);
        }
        Map<Node, List<Node>> cache = new HashMap<>();

        Node fromN = new Node(from);
        Node toN = new Node(to);

        if (! allNodes.containsKey(fromN) || ! allNodes.containsKey(toN)) {
            return -1;
        }
        fromN = allNodes.get(fromN);
        toN = allNodes.get(toN);

        List<Node> path = traverse(fromN, toN, cache);
        return path.size() - 1;
    }

    private static List<Node> traverse(Node fromN, Node toN, Map<Node, List<Node>> cache) {

        if(cache.containsKey(fromN)) {
            System.out.println("cache Hit: " + fromN);

            return cache.get(fromN);
        }
        System.out.println("visiting: " + fromN);
        if (fromN == null || fromN.visited) {
            return new ArrayList<>();
        }
        if (fromN.equals(toN)) {
            List<Node> target = new ArrayList<>();
            target.add(toN);
            return target;
        }
        fromN.visited = true;

        List<Node> parentWay = new ArrayList<>();
        List<Node> lchildWay = new ArrayList<>();
        List<Node> rchildWay = new ArrayList<>();

        parentWay.addAll(traverse(fromN.parent, toN, cache));
        lchildWay.addAll(traverse(fromN.lchild, toN, cache));
        rchildWay.addAll(traverse(fromN.rchild, toN, cache));

        List<Node> shortest = getShortestList(getShortestList(parentWay, lchildWay), rchildWay);

        cache.put(fromN, shortest);
        if (! shortest.isEmpty()) {
            shortest.add(fromN);
        }
        fromN.visited = false;
        System.out.println(shortest);
        return shortest;
    }

    private static List<Node> getShortestList(List<Node> l1, List<Node> l2 ) {
        List<Node> shortest = null;
        if (l1 != null & l2 != null) {
            if (l1.isEmpty()) {
                shortest = l2;
            } else if (l2.isEmpty()) {
                shortest = l1;
            } else {
                shortest = l1.size() < l2.size() ? l1 : l2;
            }
        } else if (l1 == null) {
            shortest = l2;
        } else if (l2 == null) {
            shortest = l1;
        }
        return shortest;
    }

    private static class Node {
        Node parent;
        Node lchild;
        Node rchild;

        final int value;
        public boolean visited;

        private Node(int value) {
            this.value = value;
        }

        public void addNode(int i, Map<Node, Node> allNodes) {
            if (i > value) {
                if (null == rchild) {
                    rchild = new Node(i);
                    rchild.parent = this;
                    allNodes.put(rchild, rchild);
                } else {
                    rchild.addNode(i, allNodes);
                }
            }
            if (i < value) {
                if (null == lchild) {
                    lchild = new Node(i);
                    lchild.parent = this;
                    allNodes.put(lchild, lchild);
                } else {
                    lchild.addNode(i, allNodes);
                }
            }
        }

        @Override
        public boolean equals(Object obj) {
            return ((Node) obj).value == value;
        }

        @Override
        public int hashCode() {
            return value;
        }

        @Override
        public String toString() {
            return String.valueOf(value);
        }
    }
}

1. Find Least common Ancestor(LCA) as we did in Q56. See both approaches to find LCA. I would prefer first approach as it stores the path of each node also which we can use to find distance b/w node to LCA
2. Now count the number of nodes in path 1 and path 2. Total distnace/vertices will be (Path 1 Nodes -1) + (Path2 Nodes -1)