Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Inorder tree traversal: Which definition is correct?

Tags:

I have the following text from an academic course I took a while ago about inorder traversal (they also call it pancaking) of a binary tree (not BST):

Inorder tree traversal

Draw a line around the outside of the tree. Start to the left of the root, and go around the outside of the tree, to end up to the right of the root. Stay as close to the tree as possible, but do not cross the tree. (Think of the tree — its branches and nodes — as a solid barrier.) The order of the nodes is the order in which this line passes underneath them. If you are unsure as to when you go “underneath” a node, remember that a node “to the left” always comes first.

Here's the example used (slightly different tree from below)

tree 1

However when I do a search on google, I get a conflicting definition. For example the wikipedia example:

Tree definition

Inorder traversal sequence: A, B, C, D, E, F, G, H, I (leftchild,rootnode,right node)

But according to (my understanding of) definition #1, this should be

A, B, D, C, E, F, G, I, H

Can anyone clarify which definition is correct? They might be both describing different traversal methods, but happen to be using the same name. I'm having trouble believing the peer-reviewed academic text is wrong, but can't be certain.

like image 406
Chris S Avatar asked Jan 28 '09 00:01

Chris S


People also ask

What is correct about the inorder traversal?

Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)? Explanation: An Inorder traversal of a Binary Search Tree must be in increasing order.

What is inorder traversal example?

Example of inorder traversalThe nodes with yellow color are not visited yet. Now, we will traverse the nodes of the above tree using inorder traversal. Here, 40 is the root node. We move to the left subtree of 40, that is 30, and it also has subtree 25, so we again move to the left subtree of 25 that is 15.


1 Answers

In my bad attempt at the drawing here's the order that shows how they should be picked. alt text

pretty much pick the node that is directly above the line being drawn,.

like image 72
John Boker Avatar answered Oct 14 '22 14:10

John Boker