CODEWITHSUNDEEP
algorithmrecursionbinary-treedynamic-programming
user270386
user270386

Reputation: 333

Distance between root and node in binary tree using recursion

I read an algorithm to find distance between two nodes in binary tree. In that distance from root to node and lowest common ancestor of given nodes is needed.
This piece of code finds (1 + distance from root to given node) in a binary tree.

 int Pathlength(Node* root, int n1) {
        if (root != NULL) {
            int x=0;
            if ((root->data == n1) || (x=Pathlength(root->left, n1))>0||(x=Pathlength(root->right, n1))>0) 
            {

                return x + 1;
            }
            return 0;
        }
     return 0;
    }

What I don't understand is 'x' has both the values, one from left-subtree and another from right-subtree, how does it know which value to return?
For example if tree is like : 

20  
/  \  
8  2

Then on calling Pathlength(root, 8), 

x=Pathlength(root->left,8)=1  
x=Pathlength(root->right,2)=0

So, in statement "return x+1", how does it return the correct x's value?

Upvotes: 0

Views: 1499

Answers (1)

NeoWang
NeoWang

Reputation: 18563

You need to understand in C/C++, the logical OR || is short-circuit:

When evaluating A || B, if A is True, B is not evaluated (since A||B will always be True no matter what B is).

In this expression:

(root->data == n1) || (x=Pathlength(root->left, n1))>0||(x=Pathlength(root->right, n1))>0

Since Pathlength(root->left, n1) is 1, it is assigned to x, and x>0 evaluates to True, x=Pathlength(root->right, n1) is no longer called.

Upvotes: 1

Related Questions