Distance between 2 nodes in a BST

Problem Statement

In a Binary Search Tree containing unique integers, find the distance between 2 nodes given access to those 2 nodes and the root of the BST. The distance between 2 nodes P and Q is the number of edges on the path(traversing each edge only once) between 2 nodes.

Consider the below Tree with nodes 4, 2, 1, 3. The distance between 1 and 3 is 2

Approach

• To find the distance between 2 nodes, we find the Lowest Common Ancestor(LCA) between the 2 nodes.
• Find the distance between NodeP to LCA and NodeQ to LCA.
• The sum of the above 2 distances is the total distance between NodeP and NodeQ

Run Time Complexity

The Time complexity of this code is O(n). That is because find the LCA is costing O(n) and calculating the distance between LCA and a Node is O(logn), so the higher order term would cost O(n).

However, we can find the LCA in a BST in O(logn) , please see this post here. This can be done when we do not have to search NodeP and NodeQ. So the cost can be reduced to O(logn).

/**
     * Calculate distance between the 2 nodes of a Binary Search Tree
     * @param nodeA
     * @param nodeB
     * @return the distance
     */
     static int getDistanceBetweenNodes(TreeNode root, TreeNode nodeA, TreeNode nodeB){
        int distance = 0;
        TreeNode lca = LCA(root, nodeA, nodeB);
        return (getDistanceFromLCA(lca,nodeA,distance) + getDistanceFromLCA(lca,nodeB,distance));
    }
/**
     * Calculate the distance between the node and its lowest common ancestor and
     * @param ancestor
     * @param child
     * @param distance
     * @return distance(number of edges on the path between them)
     */
     static int getDistanceFromLCA(TreeNode ancestor, TreeNode child, int distance){
        if (ancestor == child){
            return distance;
        }if((child == ancestor.left) || (child == ancestor.right)){
            distance +=1;
            return distance;
        }if (child.val < ancestor.val){
            distance += 1;
            return getDistanceFromLCA(ancestor.left,child,distance);
        }distance +=1;
        return getDistanceFromLCA(ancestor.right,child,distance);
    }
/**
     * Find the lowest common ancestor of two nodes A and B given the root node
     * @param root
     * @param nodeA
     * @param nodeB
     * @return lowest common ancestor
     */
     static TreeNode LCA(TreeNode root, TreeNode nodeA, TreeNode nodeB){
        if (root == null){
            return null;
        }if (nodeA == root || nodeB == root){
            return root;
        }
        TreeNode left = LCA(root.left,nodeA,nodeB);
        TreeNode right = LCA(root.right,nodeA,nodeB);
        if (left != null && right != null){
            return root;
        }
        if (left == null){
            return right;
        }else return left;
    }