# Tree: Inorder Traversal

# Tree: Inorder Traversal

ricky03cool + 2 comments def inOrder(root): if root: inOrder(root.left) print(root.data, end=" ") inOrder(root.right)

chernandez2 + 3 comments Honestly, I don-t understand how this algorithm works.

I can imagine this tree

`5 \ 1 /\ 6 3 / \ 2 4`

Doing your algorithm,the output is: 5,2,6,4,1,3.

Where is the order in there?

Kind Regards,

- BG
BansheeGhoul + 0 comments [deleted] - BG
BansheeGhoul + 1 comment Your Binary tree (shown) is not correct,

Binary tree algo : if new value is small to previous value goes to left or else goes to rigth of previous value

Put your values as input in his code you will see correct output which is 1,2,3,4,5,6

jura_z + 0 comments [deleted]

- DY
dougyoung + 0 comments OP's solution assumes that the binary tree is in fact an ordered binary tree (aka binary

*search*tree): in other words a tree where each left child node is less than its parent node's value and each right child node is greater than its parent node's value.The problem doesn't specify this constraint, though the submission tests don't seem to violate the assumption either. Either OP's assumption is incorrect and happens to work against the test cases or the challenge is not written as clearly as it could be.

UmkaFrom + 0 comments brilliant

ZeaLot4J + 3 comments Java solution without recursion

void inOrder(Node root) { Deque<Node> stack = new ArrayDeque<Node>(); while(!stack.isEmpty() || root!=null){ if(root!=null){ stack.push(root); root = root.left; }else{ root = stack.pop(); System.out.print(root.data+" "); root = root.right; } } }

VictoriaB + 0 comments Nice. Thank you.

wqian + 0 comments Wow, smart!

bennattj + 1 comment LOL, this is virtually identical to my solution (and no I didn't check here first and resisted just "copying" the Wikipedia solution--which I just verified is exactly this). This would appear to be a pretty straightforward problem (because my previous two differed cosmetically from the Wikipedia solution).

yandrypozo + 1 comment I don't understand why these problems only accept solution with Java or C++, why not Go or Python ? :(

AllisonP + 2 comments Python is now enabled for this challenge.

garthbryden + 0 comments Enabling it for Go would be awesome too!

- JM
JohnPaul + 0 comments Python 3?

- PJ
im_priyank_jain + 2 comments Morris Traversal ## Complexity => Time :: O(n) | Space :: O(1)

void inOrder(Node root) { Node pre; if(root == null) return; Node curr = root; while(curr != null){ if(curr.left == null){ System.out.print(curr.data+" "); curr = curr.right; }else{ pre = curr.left; while(pre.right !=null && pre.right != curr) pre = pre.right; if(pre.right == null){ pre.right = curr; curr = curr.left; }else{ pre.right=null; System.out.print(curr.data+" "); curr=curr.right; } } } }

ZeaLot4J + 0 comments That's awesome, now I've got a new skill.

- CL
tigerleapgorge + 0 comments Beautifully done.

- MM
maddman + 1 comment @shashank21j the problem has very weak test cases.

- EW
ewoodg + 0 comments What kind of test cases you think it is missing?

- RR
rommims + 0 comments Python 3?

- JS
josteier + 1 comment For the Inorder Traversal, it goes to the left, to the root area("starting point" of the tree) and then to the right, so for the sample input/output it shouldn't be 1 2 3 4 5 6 , it should be 3 4 1 2 5 6, right? They never said it was a BST or anything else, so the sample I/O must be wrong.

- EM
ezmarte + 0 comments Given the array as is it shouldn't be. However in this program it seems the child nodes are all predefined with that being the case there is nothing pointing to left of 1 both in terms of value and on the tree itself, so it can't print anything. The program then prints 1 first because it's the root then the program looks at the right of the root and then the process repeats itself.

- JM
JohnPaul + 0 comments No Python 3 in my dropdown. Should this be so?

Mohit_MR + 0 comments `void inOrder(node *root) { node* current,* pre; current=root; while(current){ if(!current->left){ cout<<current->data<<" "; current=current->right; }else { pre=current->left; while(pre->right&&pre->right!=current) pre=pre->right; if(!pre->right){ pre->right=current; current=current->left; }else { pre->right=NULL; cout<<current->data<<" "; current=current->right; } } }`

} Morris algo without using stack and recursion

- DJ
Dharmanshu + 0 comments void inOrder(node *root) {

`if (root) { inOrder(root->left); printf("%d ",root->data); inOrder(root->right); }`

}

Sort 58 Discussions, By:

Please Login in order to post a comment