Find Distance In A Binary Tree - Leetcode Solution

Problem Statement:

Given the root of a binary tree and two nodes, p and q, find the distance between them in the tree. The distance between two nodes is the number of edges on the path from one of these nodes to the other.

Solution Approach:

To solve the given problem, we can follow the below approach:

1. We need to first find the Lowest Common Ancestor (LCA) of the given two nodes p and q in the binary tree.

2. Once we have found the LCA, we can calculate the distance between the LCA and the two nodes p and q separately.

3. The total distance between the two nodes p and q would then be the addition of the distances between the LCA and the two nodes.

To find the LCA, we can use the following procedure:

1. We can start by traversing the tree from the root node.

2. Once we encounter either one of the nodes p or q, we can return that node as the LCA.

3. If we do not find either of the nodes, we can recursively find the LCA in the left and right subtrees of the current node.

4. If we find the nodes in different subtrees of the current node, we can return the current node as the LCA.

To calculate the distance between the LCA and the two nodes p and q separately, we can use the following procedure:

1. We can start by traversing the tree from the LCA node.

2. We can keep track of the distance between the current node and the target node until we reach the target node.

3. Finally, we can return the distance as the result.

The complete solution for the given problem is as follows:

Algorithm:

1. Find the Lowest Common Ancestor (LCA) of the given two nodes p and q in the binary tree.
2. Calculate the distance between the LCA and the two nodes p and q separately.
3. The total distance between the two nodes p and q would then be the addition of the distances between the LCA and the two nodes.

Code:

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL || root == p || root == q) {
            return root;
        }
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left != NULL && right != NULL) {
            return root;
        }
        if (left != NULL) {
            return left;
        }
        return right;
    }
    
    int distance(TreeNode* root, TreeNode* target) {
        if (root == NULL) {
            return -1;
        }
        if (root == target) {
            return 0;
        }
        int left = distance(root->left, target);
        int right = distance(root->right, target);
        if (left != -1) {
            return left + 1;
        }
        if (right != -1) {
            return right + 1;
        }
        return -1;
    }

    int findDistance(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* lca = lowestCommonAncestor(root, p, q);
        int dist_p = distance(lca, p);
        int dist_q = distance(lca, q);
        return dist_p + dist_q;
    }
};

Time Complexity Analysis:

Finding the LCA of the tree takes O(n) time, where n is the number of nodes in the tree.

Finding the distance between the LCA and the two nodes takes O(n) time for each node, where n is the number of nodes in the tree.

Therefore, the overall time complexity of the solution is O(n).

1