DistanceOfNodesInBST.java

/**
 * @author gohar.gasparyan
 */
public class DistanceOfNodesInBST {

    public static void main(String[] args) {
        testFindDistance();
    }

    private static void testFindDistance() {
        BinarySearchTree bst = new BinarySearchTree();
        bst.insert(20);
        bst.insert(15);
        bst.insert(25);
        bst.insert(10);
        bst.insert(18);
        bst.insert(16);
        bst.insert(19);
        bst.insert(17);

        System.out.println("Distance between 20, 20 is" + findDistance(bst.root, 20, 20));
        System.out.println("Distance between 20, 25 is" + findDistance(bst.root, 20, 25));
        System.out.println("Distance between 17, 19 is" + findDistance(bst.root, 17, 19));
        System.out.println("Distance between 17, 25 is" + findDistance(bst.root, 17, 25));
    }

    private static int findDistance(Node root, int value1, int value2) {
        int lcaData = findLCA(root, value1, value2).value;
        return findDistance(root, value1) + findDistance(root, value2) - 2 * findDistance(root, lcaData);
    }

    private static int findDistance(Node root, int value) {
        if (root == null) {
            throw new RuntimeException("Value: " + value + " doesnt exist in BST.");
        }

        if (value == root.value) {
            return 0;
        }

        if (value > root.value) {
            return 1 + findDistance(root.right, value);
        } else {
            return 1 + findDistance(root.left, value);
        }
    }

    private static Node findLCA(Node root, int value1, int value2) {
        if (root != null) {
            int rootValue = root.value;

            if (rootValue == value1 || rootValue == value2) {
                return root;
            }

            if (value1 > rootValue && value2 > rootValue) {
                return findLCA(root.right, value1, value2);
            }

            if (value1 < rootValue && value2 < rootValue) {
                return findLCA(root.left, value1, value2);
            }

            return root;
        }

        return null;
    }

    static class Node {
        int value;
        Node left;
        Node right;

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

    static class BinarySearchTree {

        Node root;

        public BinarySearchTree() {
        }

        public void insert(int value) {
            Node newNode = new Node(value);
            if (root == null) {
                root = newNode;
                return;
            }

            Node current = root;
            Node parent;

            while (true) {
                parent = current;
                if (current.value > value) {
                    current = current.left;

                    if (current == null) {
                        parent.left = newNode;
                        return;
                    }

                } else {
                    current = current.right;
                    if (current == null) {
                        parent.right = newNode;
                        return;
                    }
                }
            }
        }
    }
}