Find distance between two nodes of a Binary Tree

Find the distance between two keys in a binary tree, no parent pointers are given. Distance between two nodes is the minimum number of edges to be traversed to reach one node from other.

class Solution {
    Node lca;
    int d1Depth;
    int d2Depth;
    int lcaDepth;

    public boolean lca(Node node, int d1, int d2, int level) {
        if (node == null) {
            return false;
        }

        boolean self = false;

        if (node.data == d1) {
            d1Depth = level;
            self = true;
        }
        if (node.data == d2) {
            d2Depth = level;
            self = true;
        }

        boolean left = lca(node.left, d1, d2, level + 1);
        boolean right = lca(node.right, d1, d2, level + 1);

        // moment of reckoning
        // both child found something
        // one child or self found something
        if ((left == true && right == true) || (left == true && self == true) || (self == true && right == true)) {
            if (lca == null) {
                lca = node;
                lcaDepth = level;
            }
        }
        return self || left || right;
    }

    public int distance(Node root, int p, int q) {
        lca(root, p, q, 0);
        return (d1Depth + d2Depth - 2 * lcaDepth);
    }
}

Last updated