Distance between root and node in binary tree using recursion

Question

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?

NeoWang NeoWang · Accepted Answer · 2015-08-30T12:54:37

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.

Distance between root and node in binary tree using recursion

1 Answers