Distance between two nodes in a binary tree

In this blog, you will get to know how to find the distance between two nodes in a binary tree. 

So, let’s start the blog:

Algorithm to find the distance between two nodes in binary tree:

So, to find the distance between two nodes in a binary tree, we have to:

1. Firstly, we will find the lowest common ancestor (LCA) of that two nodes.
2. Then, we have to calculate the distance of each node to the LCA.
3. Finally, we have to add the distances to get the final distance between that two nodes.

Find the distance between two nodes in a binary tree code:

Code:

So, here is the code to find the distance between two nodes in binary tree:

#include <iostream>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val){
        
        this->val=val;
        left=NULL;
        right=NULL;
    }
};


// Function to find the lowest common ancestor (LCA) of two nodes
TreeNode* findLCA(TreeNode* root, int n1, int n2) {
    if (root == NULL || root->val == n1 || root->val == n2) {
        return root;
    }

    TreeNode* leftLCA = findLCA(root->left, n1, n2);
    TreeNode* rightLCA = findLCA(root->right, n1, n2);

    if (leftLCA != NULL && rightLCA != NULL) {
        return root; // If nodes are present in both left and right subtrees, then the current node is the LCA.
    }

    return (leftLCA != NULL) ? leftLCA : rightLCA;
}

// Function to calculate the distance between a node and its ancestor
int findDistanceToAncestor(TreeNode* root, int node_val, int distance) {
    if (root == NULL) {
        return -1;
    }

    if (root->val == node_val) {
        return distance;
    }

    int leftDistance = findDistanceToAncestor(root->left, node_val, distance + 1);
    if (leftDistance != -1) {
        return leftDistance;
    }

    return findDistanceToAncestor(root->right, node_val, distance + 1);
}

// Function to calculate the distance between two nodes in a binary tree
int findDistance(TreeNode* root, int n1, int n2) {
    TreeNode* lca = findLCA(root, n1, n2);

    int distance_n1 = findDistanceToAncestor(lca, n1, 0);
    int distance_n2 = findDistanceToAncestor(lca, n2, 0);

    return distance_n1 + distance_n2;
}

int main() {
    // Example binary tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);
    root->right->left->right = new TreeNode(8);

    int node1 = 4;
    int node2 = 5;

    int distance = findDistance(root, node1, node2);
    std::cout << "Distance between nodes " << node1 << " and " << node2 << " is: " << distance << std::endl;

    // Remember to free the memory allocated for the tree (not shown in this example).
    return 0;
}

Explanation of the above code:

1. Firstly, we have to start the code, by making a struct TreeNode structure to represent a node in a binary tree. 

So, this structure will contain three members that is value, TreeNode* left and TreeNode* right to store pointers to the left and right child nodes, Also, we will make the constructor initialise the node’s value and set the left and right pointers to NULL.

2. Secondly, we will make a “findLCA” function to find the Lowest Common Ancestor of any two given nodes n1 and n2 in a binary tree. 

3. After this, we will implement the above function using recursion. Here, the base cases of the recursion are:

• Firstly, we will check if the current node “root” is equal to NULL or not.
• Or if its value is equal to either n1 or n2, then it is the value of LCA. So, the function will return the root value.

4. Otherwise, it will recursively search for “n1” and “n2” in the left and right subtrees of the current node using the “findLCA” function.

5. If both n1 and n2 are found in different subtrees, then the current node “root” is the LCA, and the function returns “root”.

6. Next, we will make the “findDistanceToAncestor” function to calculate the distance between a node with a given value `node_val` and its ancestor. This function will also use the recursion approach to traverse the binary tree from the “root” to find the node with the specified value.

7. So, this function will return -1 if the node with the value “node_val” is not found in the subtree.

 8. If the node with the value “node_val” is found, the function returns the distance from the current node “root” to the node with the value “node_val”.

9. Next we will make a “findDistance” function to calculate the distance between two nodes with values “n1” and “n2” in a binary tree.

• So, it finds the Lowest Common Ancestor of the two nodes using the findLCA function.

• Then, it calculates the distance of each node n1 and n2 to the LCA using the findDistanceToAncestor function.

10. Finally, it returns the sum of these distances, which gives the total distance between nodes n1 and n2.

Output: