# Tree: Inorder Traversal

# Tree: Inorder Traversal

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).

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,

BansheeGhoul + 0 comments [deleted]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]

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

im_priyank_jain + 4 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.

tigerleapgorge + 0 comments Beautifully done.

cellepo + 0 comments Thanks for helping to discover Morris' exists!

Here is my Java solution of essentially the same (passes all tests) with code comments:

public static void inOrder(Node root) { Node cur = root; while(cur != null){ if(cur.left != null){ // Find in-order predecessor of cur Node curPredecessor = cur.left; while(curPredecessor.right != null && curPredecessor.right != cur){ curPredecessor = curPredecessor.right; } // curPredecessor now indeed is the predecessor of cur if(curPredecessor.right == null){ // Thread curPredecessor back to cur (to "remember" it without a stack) curPredecessor.right = cur; // "Recur" to left cur = cur.left; } else { System.out.print(cur.data + " "); // "Recur" to right cur = cur.right; } } else { System.out.print(cur.data + " "); // "Recur" to right cur = cur.right; } } }

cellepo + 0 comments FWIW: Here is some helpful compexity analysis of Moriss': https://stackoverflow.com/questions/6478063/how-is-the-time-complexity-of-morris-traversal-on/

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!

JohnPaul + 0 comments Python 3?

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

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

}

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

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

rommims + 0 comments Python 3?

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

jlama + 0 comments Using a Stack, withour recursion :)

public static void inOrder(Node root) { Stack<Node> stack = new Stack<>(); while (true) { // Push all the nodes from the left. while(root != null) { stack.push(root); root = root.left; } // check if the stack is empty. if (stack.isEmpty()) { return; } // pop them and print their data. Then go to the right. root = stack.pop(); System.out.print(root.data + " "); root = root.right; } }

Sort 66 Discussions, By:

Please Login in order to post a comment