Solved

Traversal in Binary tree in c++

Posted on 2009-03-30
1
940 Views
Last Modified: 2013-11-17
there is a three line code using recursion for inorder traversal . I am not able to understand the logic.  the code is :

in(node *p)
if(p!=NULL)
{
in(p->l);
cout << p->data;
in(p->r);
}

I can understand that the flow is towards the last node which is less than  the root where both the left and right are null.  How the pointer climbs from left to root and then to right.  Please explain
0
Comment
Question by:abdul_mujeeb
1 Comment
 
LVL 45

Accepted Solution

by:
Kdo earned 500 total points
ID: 24018241
Hi abdul,

It help a lot if you can visualize the tree.  Here's a sorted tree as an example:

              6
            /   \
          3     8
        /   \     \
       1    4     9
         \
          2

Note that all of the sort rules apply.  All of the child nodes to the left of the node are smaller, all of the child nodes to the right are larger.

Using your small function, we start at root.  Root has a value of 6, and most importantly, a left child.  So the function recursively calls itself passing the left child (value 3).  

Now the process is repeated with 3 as the current node.  3 has a left child so the function recursively calls itself passing the left child (value 1) and the process repeats again.  

The node with a value of 1 does not have a left child.  Still, the function calls itself passing the left child (NULL).  The function detects the NULL and simply returns.  Now the fun starts.  :)

Upon returning to the function that is using the node with a value of 1, the function prints the value to output.  It then calls inselft passing the right child (value 2).

The node with a value of 2 doesn't have a left child so the call is again trivial as it simply returns.  The function then prints the value to output and calls itself with the right child which is also NULL and simply returns to the call that is processing the node with a value of 2.

That call (value 2) returns to the caller (value 1) which returns to its caller (value 3).  It then prints 3 to output and processes the right child (value 4).

That process continues until the entire tree is displayed.


Good Luck,
Kent
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
What xml editor to use. 8 84
Visual Studio C# project complains it can't run a dll 5 91
Change local server setting in php 6 81
Syntax Error 2 41
In our object-oriented world the class is a minimal unit, a brick for constructing our applications. It is an abstraction and we know well how to use it. In well-designed software we are not usually interested in knowing how objects look in memory. …
Programmer's Notepad is, one of the best free text editing tools available, simply because the developers appear to have second-guessed every weird problem or issue a programmer is likely to run into. One of these problems is selecting and deleti…
The viewer will learn how to use NetBeans IDE 8.0 for Windows to connect to a MySQL database. Open Services Panel: Create a new connection using New Connection Wizard: Create a test database called eetutorial: Create a new test tabel called ee…
The viewer will learn how to use and create new code templates in NetBeans IDE 8.0 for Windows.

947 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now