Binary Tree

Min distance between two nodes of a Binary Tree

class Solution {
public:
    Node* lowestCommonAncestor(Node* root, int a, int b) {
        if (!root || root->data == a || root->data == b)
            return root;

        Node* leftLCA = lowestCommonAncestor(root->left, a, b);
        Node* rightLCA = lowestCommonAncestor(root->right, a, b);

        if (leftLCA && rightLCA)
            return root;

        return leftLCA ? leftLCA : rightLCA;
    }

    int distanceFromNode(Node* root, int target, int distance) {
        if (!root)
            return -1;

        if (root->data == target)
            return distance;

        int leftDistance = distanceFromNode(root->left, target, distance + 1);
        if (leftDistance != -1)
            return leftDistance;

        return distanceFromNode(root->right, target, distance + 1);
    }

    int findDist(Node* root, int a, int b) {
        Node* lca = lowestCommonAncestor(root, a, b);

        int distanceToA = distanceFromNode(lca, a, 0);
        int distanceToB = distanceFromNode(lca, b, 0);

        return distanceToA + distanceToB;
    }
};