CODEWITHSUNDEEP
data-structuresgraph-algorithmtree-traversalinorder
Ali Mustafa
Ali Mustafa

Reputation: 565

Problems with in-order tree traversal

I found this picture at Wikipedia: enter image description here

According to the text underneath the picutre, the in-order is: A, B, C, D, E, F, G, H, I

I understand the order A-F, but what I don't understand is the order of the last three nodes. Is it not supposed to be H, I, G? I thought you were supposed to list internal nodes on your 2nd encounter and leaves on your 1st?

EDIT: would my order be correct if the tree in the picture was a general tree and not a binary tree? (So that G would have only one node, instead of a right node and a null left node.)

Upvotes: 0

Views: 682

Answers (3)

user5034652
user5034652

Reputation:

Unfortunately Wikipedia is right!

Detailed Algorithm

inorder_traversal(node)
{
    if(node!=NULL)
       {
           inorder_traversas(node->left);                          
           print(node->data);         //you overlooked this statement on reaching G
           inorder_traversal(node->right);              
       }
}

Where are you missing the point/going the wrong way?

On reaching G from F, you tried to enter into left child of G which is NULL (in short inorder_traversal(node->left) statement failed as the algorithm has checked if(node!=NULL) and G's left child is NULL, so after that it again comes back to G, after that you overlooked the print statement which would have printed G there - after overlooking that print statement you jumped to the next statement which checked if node->right is NULL or not - you found it not null (which took you to I). Then you didn't print I directly and checked for its left child. As left child H was there, so you printed it and then you returned to I - the parent, its right child was null. Hence wikipedia is right.

Tip for testing inorder traversal : Make a binary tree which accepts integer (or numbers generally) as input data, when you'll traverse in inorder fashion, digits will be printed in ascending order.

Upvotes: 4

Pranjal
Pranjal

Reputation: 689

The answer that has been mentioned by wikipedia is correct. You said you understood A-F, so I will get from G.

In-order traversal follows the series: left-parent-right. So when F is traversed and the algorithm goes to the right child of F, it first encounters G and then tries to locate the left child of G. Since the left child of G is null, nothing is printed and then it goes to the parent, that is, G; so G is printed. Now, it goes to the right child of G which is I. Now, it locates the left child of I which is H and prints it. Then it returns to the parent that is I and prints it. It then traverses to the right of I and finds that it is null. Now as all the nodes have been traversed, the algorithm terminates. Thus the order is G H I

Upvotes: 1

MrGreen
MrGreen

Reputation: 499

In-order traversal works like this:

1- print the left sub tree.
2- print the root.
3- print the right sub tree

In the example you provided:

1- the left sub-tree of `G` is empty, so we do not print any thing.
2- we print the node `G`.
3- finally we print the right sub-tree of `G`

Upvotes: 0

Related Questions