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 · Accepted Answer · 2015-08-30 12:54:37Z

1

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.

answered Aug 30, 2015 at 12:54

NeoWang

18.8k24 gold badges87 silver badges134 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Distance between root and node in binary tree using recursion

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related