CODEWITHSUNDEEP
c++recursiondata-structuresbinary-tree
Nick Hill
Nick Hill

Reputation: 71

How tree traversals work?

This is the code for preOrder traversal -

void preOrder(node *root) 
{    
    if(root!=NULL)
    {
        cout<<root->data<<" ";
        preOrder(root->left);
        preOrder(root->right);
    }         
}

When we've reached the last node on the left, how does it go to the right node? I mean there is no link between left and right node though they both have same parent but after reaching the last node how does it go back to its parent?

Upvotes: 1

Views: 590

Answers (2)

Shivam Arora
Shivam Arora

Reputation: 496

Yes! There is no direct link between two children of a same node.

Now to help you out with the above recursion code, look at the following image taken from geeksforgeeks.

enter image description here

Jumping straight to the left most node 4 , as you know how you reached there, let's now understand how it is moving back to its parent and so on and so forth.

When you will come out of the following line which you will definitely because of if(root!=NULL) as the left child and right child of 4 is null, still not get it? Don't worry, see the following explanation.

Now, you are at the left most node which is 4 in this case, the line which is responsible for reaching to this node is:

preOrder(root->left) and you have not seen what is beneath this line till now

i.e. you have never seen the following line:

preOrder(root->right);.

Left child of 4 is null, because of which the recursion condition breaks and you finally see preOrder(root->right); .This is not some kind of sorcery, this is what recursion is. Now when you see the right child of 4 which is again null.

well, what is the value of root now ?

The value of root is 2 because 2 is the only value which took you to the 4 at the first place. Recursion is like level inside a level, and when the last level finishes off, the call goes back to the level above it which is 2 for 4. And finally the following line will take it to the right child of 2 which is 5.

preOrder(root->right);

Take away:

1)Whenever you see cout<<root->data<<" "; you print the current root's value.

2)Whenever you see preOrder(root->left); you move to the left child of root.

3)Whenever you see preOrder(root->right); you move to the right child of root.

4)If the value of root is NULL you do nothing and you will be taken back to the calling line which will be either of preOrder(root->left); or preOrder(root->right);.

If we follow what I said above you can guess the preOrder traversal for the given binary tree which will be:

1 2 4 5 3

Now, I advise you to read and learn recursion and then approach the above problem again.

Upvotes: 2

vencik
vencik

Reputation: 86

You are calling the function recursively. Each call to preOrder creates what we call a frame on the thread's execution stack. These frames follow each path in the tree. When you return from the function, its call frame is removed (or "popped") from the stack and the control returns to the previous frame.

That's why, when you reach a leaf, you "back-track" to parent and then to the sibling sub-tree (via the 2nd call to preOrder). The "link" you talk of is actually created on the execution stack.

Upvotes: 0

Related Questions