Help me understand Inorder Traversal without using recursion

Question

I am able to understand preorder traversal without using recursion, but I'm having a hard time with inorder traversal. I just don't seem to get it, perhaps, because I haven't understood the inner working of recursion.

This is what I've tried so far:

def traverseInorder(node): lifo = Lifo() lifo.push(node) while True: if node is None: break if node.left is not None: lifo.push(node.left) node = node.left continue prev = node while True: if node is None: break print node.value prev = node node = lifo.pop() node = prev if node.right is not None: lifo.push(node.right) node = node.right else: break

The inner while-loop just doesn't feel right. Also, some of the elements are getting printed twice; may be I can solve this by checking if that node has been printed before, but that requires another variable, which, again, doesn't feel right. Where am I going wrong?

I haven't tried postorder traversal, but I guess it's similar and I will face the same conceptual blockage there, too.

Thanks for your time!

P.S.: Definitions of Lifo and Node:

class Node: def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right class Lifo: def __init__(self): self.lifo = () def push(self, data): self.lifo = (data, self.lifo) def pop(self): if len(self.lifo) == 0: return None ret, self.lifo = self.lifo return ret

related · Accepted Answer · 2014-02-17 21:32:16Z

Start with the recursive algorithm (pseudocode) :

traverse(node): if node != None do: traverse(node.left) print node.value traverse(node.right) endif

This is a clear case of tail recursion, so you can easily turn it into a while-loop.

traverse(node): while node != None do: traverse(node.left) print node.value node = node.right endwhile

You're left with a recursive call. What the recursive call does is push a new context on the stack, run the code from the beginning, then retrieve the context and keep doing what it was doing. So, you create a stack for storage, and a loop that determines, on every iteration, whether we're in a "first run" situation (non-null node) or a "returning" situation (null node, non-empty stack) and runs the appropriate code:

traverse(node): stack = [] while !empty(stack) || node != None do: if node != None do: // this is a normal call, recurse push(stack,node) node = node.left else // we are now returning: pop and print the current node node = pop(stack) print node.value node = node.right endif endwhile

The hard thing to grasp is the "return" part: you have to determine, in your loop, whether the code you're running is in the "entering the function" situation or in the "returning from a call" situation, and you will have an if/else chain with as many cases as you have non-terminal recursions in your code.

In this specific situation, we're using the node to keep information about the situation. Another way would be to store that in the stack itself (just like a computer does for recursion). With that technique, the code is less optimal, but easier to follow

traverse(node): // entry: if node == NULL do return traverse(node.left) // after-left-traversal: print node.value traverse(node.right) traverse(node): stack = [node,'entry'] while !empty(stack) do: [node,state] = pop(stack) switch state: case 'entry': if node == None do: break; // return push(stack,[node,'after-left-traversal']) // store return address push(stack,[node.left,'entry']) // recursive call break; case 'after-left-traversal': print node.value; // tail call : no return address push(stack,[node.right,'entry']) // recursive call end endwhile

@Victor: Thank you! Your hint to think about the parts of code that have to be run in "entering-the-function" situation and "returning-from-a-call" situation helped me understand intuitively. Also, thanks for the intermediate step where you unwound the tail-recursion; I've heard about it, but seeing it in action helped a lot!
That's a nice explanation... I figured the same in an difficult way.. But the above way of step-by-step breakdown has made it understand very simpler
I don't think traverse(node): if node != None do: traverse(node.left) print node.value traverse(node.right) endif is tail recursive
I agree with @JacksonTale. This is definitely not a clear case of tail recursion. Tail recursion requires a single recursive call. Recursive tree traversal is actually a typical example of non-tail-recursion.
Hi @Victor, That's the best article on this topic. Can you elaborate pre_order_traversal and post_order_traversal as well? ^_^

Emadpres · Accepted Answer · 2012-02-17 06:00:33Z

Here is a simple in-order non-recursive c++ code ..

void inorder (node *n) { stack s; while(n){ s.push(n); n=n->left; } while(!s.empty()){ node *t=s.pop(); cout<<t->data; t=t->right; while(t){ s.push(t); t = t->left; } } }

funnydman · Accepted Answer · 2022-07-27 17:57:47Z

def print_tree_in(root): stack = [] current = root while True: while current is not None: stack.append(current) current = current.getLeft(); if not stack: return current = stack.pop() print current.getValue() while current.getRight is None and stack: current = stack.pop() print current.getValue() current = current.getRight();

Henk Holterman · Accepted Answer · 2010-01-22 11:06:20Z

def traverseInorder(node): lifo = Lifo() while node is not None: if node.left is not None: lifo.push(node) node = node.left continue print node.value if node.right is not None: node = node.right continue node = lifo.Pop() if node is not None : print node.value node = node.right

PS: I don't know Python so there may be a few syntax issues.

Community · Accepted Answer · 2017-05-23 12:25:19Z

Here is a sample of in order traversal using stack in c# (.net):

(for post order iterative you may refer to: Post order traversal of binary tree without recursion)

public string InOrderIterative() { List<int> nodes = new List<int>(); if (null != this._root) { Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>(); var iterativeNode = this._root; while(iterativeNode != null) { stack.Push(iterativeNode); iterativeNode = iterativeNode.Left; } while(stack.Count > 0) { iterativeNode = stack.Pop(); nodes.Add(iterativeNode.Element); if(iterativeNode.Right != null) { stack.Push(iterativeNode.Right); iterativeNode = iterativeNode.Right.Left; while(iterativeNode != null) { stack.Push(iterativeNode); iterativeNode = iterativeNode.Left; } } } } return this.ListToString(nodes); }

Here is a sample with visited flag:

public string InorderIterative_VisitedFlag() { List<int> nodes = new List<int>(); if (null != this._root) { Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>(); BinaryTreeNode iterativeNode = null; stack.Push(this._root); while(stack.Count > 0) { iterativeNode = stack.Pop(); if(iterativeNode.visted) { iterativeNode.visted = false; nodes.Add(iterativeNode.Element); } else { iterativeNode.visted = true; if(iterativeNode.Right != null) { stack.Push(iterativeNode.Right); } stack.Push(iterativeNode); if (iterativeNode.Left != null) { stack.Push(iterativeNode.Left); } } } } return this.ListToString(nodes); }

the definitions of the binarytreenode, listtostring utility:

string ListToString(List<int> list) { string s = string.Join(", ", list); return s; } class BinaryTreeNode { public int Element; public BinaryTreeNode Left; public BinaryTreeNode Right; }

yask · Accepted Answer · 2016-10-08 14:06:34Z

Simple iterative inorder traversal without recursion

'''iterative inorder traversal, O(n) time & O(n) space ''' class Node: def __init__(self, value, left = None, right = None): self.value = value self.left = left self.right = right def inorder_iter(root): stack = [root] current = root while len(stack) > 0: if current: while current.left: stack.append(current.left) current = current.left popped_node = stack.pop() current = None if popped_node: print popped_node.value current = popped_node.right stack.append(current) a = Node('a') b = Node('b') c = Node('c') d = Node('d') b.right = d a.left = b a.right = c inorder_iter(a)

user283368 · Accepted Answer · 2010-03-01 03:40:21Z

State can be remembered implicitly,

traverse(node) { if(!node) return; push(stack, node); while (!empty(stack)) { /*Remember the left nodes in stack*/ while (node->left) { push(stack, node->left); node = node->left; } /*Process the node*/ printf("%d", node->data); /*Do the tail recursion*/ if(node->right) { node = node->right } else { node = pop(stack); /*New Node will be from previous*/ } } }

Negative. This version gets stuck in an infinite loop around the bottom of the tree.

Leonmax · Accepted Answer · 2011-07-31 02:25:41Z

@Victor, I have some suggestion on your implementation trying to push the state into the stack. I don't see it is necessary. Because every element you take from the stack is already left traversed. so instead of store the information into the stack, all we need is a flag to indicate if the next node to be processed is from that stack or not. Following is my implementation which works fine:

def intraverse(node): stack = [] leftChecked = False while node != None: if not leftChecked and node.left != None: stack.append(node) node = node.left else: print node.data if node.right != None: node = node.right leftChecked = False elif len(stack)>0: node = stack.pop() leftChecked = True else: node = None

om471987 · Accepted Answer · 2015-09-11 03:37:17Z

Little Optimization of answer by @Emadpres

def in_order_search(node): stack = Stack() current = node while True: while current is not None: stack.push(current) current = current.l_child if stack.size() == 0: break current = stack.pop() print(current.data) current = current.r_child

Stuck in Java · Accepted Answer · 2015-11-23 23:14:53Z

This may be helpful (Java implementation)

public void inorderDisplay(Node root) { Node current = root; LinkedList<Node> stack = new LinkedList<>(); while (true) { if (current != null) { stack.push(current); current = current.left; } else if (!stack.isEmpty()) { current = stack.poll(); System.out.print(current.data + " "); current = current.right; } else { break; } } }

YakovL · Accepted Answer · 2016-10-17 00:20:39Z

class Tree: def __init__(self, value): self.left = None self.right = None self.value = value def insert(self,root,node): if root is None: root = node else: if root.value < node.value: if root.right is None: root.right = node else: self.insert(root.right, node) else: if root.left is None: root.left = node else: self.insert(root.left, node) def inorder(self,tree): if tree.left != None: self.inorder(tree.left) print "value:",tree.value if tree.right !=None: self.inorder(tree.right) def inorderwithoutRecursion(self,tree): holdRoot=tree temp=holdRoot stack=[] while temp!=None: if temp.left!=None: stack.append(temp) temp=temp.left print "node:left",temp.value else: if len(stack)>0: temp=stack.pop(); temp=temp.right print "node:right",temp.value

Welcome to SO. Please remember to add 4-space indentation to your code so that it is displayed correctly. Also, I'd recommend to add some annotation to it. OP has asked for some explanation, too, so annotation is somewhat necessary here.

jpswain · Accepted Answer · 2017-12-13 21:30:11Z

Here's an iterative C++ solution as an alternative to what @Emadpres posted:

void inOrderTraversal(Node *n) { stack<Node *> s; s.push(n); while (!s.empty()) { if (n) { n = n->left; } else { n = s.top(); s.pop(); cout << n->data << " "; n = n->right; } if (n) s.push(n); } }

Akash Kandpal · Accepted Answer · 2018-01-12 14:51:37Z

Here is an iterative Python Code for Inorder Traversal ::

class Node: def __init__(self, data): self.data = data self.left = None self.right = None def inOrder(root): current = root s = [] done = 0 while(not done): if current is not None : s.append(current) current = current.left else : if (len(s)>0): current = s.pop() print current.data current = current.right else : done =1 root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) inOrder(root)

Nitin Verma · Accepted Answer · 2021-11-07 13:15:37Z

For writing iterative equivalents of these recursive methods, we can first understand how the recursive methods themselves execute over the program's stack. Assuming that the nodes do not have their parent pointer, we need to manage our own "stack" for the iterative variants.

One way to start is to see the recursive method and mark the locations where a call would "resume" (fresh initial call, or after a recursive call returns). Below these are marked as "RP 0", "RP 1" etc ("Resume Point"). Take example of inorder traversal. (I will present in C language, but same methodology applies to any general language):

void in(node *x) { /* RP 0 */ if(x->lc) in(x->lc); /* RP 1 */ process(x); if(x->rc) in(x->rc); /* RP 2 */ }

Its iterative variant:

void in_i(node *root) { node *stack[1000]; int top; char pushed; stack[0] = root; top = 0; pushed = 1; while(top >= 0) { node *curr = stack[top]; if(pushed) { /* type (x: 0) */ if(curr->lc) { stack[++top] = curr->lc; continue; } } /* type (x: 1) */ pushed = 0; process(curr); top--; if(curr->rc) { stack[++top] = curr->rc; pushed = 1; } } }

The code comments with (x: 0) and (x: 1) correspond to the "RP 0" and "RP 1" resume points in the recursive method. The pushed flag helps us deduce one of these two resume-points. We do not need to handle a node at its "RP 2" stage, so we do not keep such node on stack.

Paolo · Accepted Answer · 2010-01-22 11:07:05Z

I think part of the problem is the use of the "prev" variable. You shouldn't have to store the previous node you should be able to maintain the state on the stack (Lifo) itself.

From Wikipedia, the algorithm you are aiming for is:

Visit the root.
Traverse the left subtree
Traverse the right subtree

In pseudo code (disclaimer, I don't know Python so apologies for the Python/C++ style code below!) your algorithm would be something like:

lifo = Lifo(); lifo.push(rootNode); while(!lifo.empty()) { node = lifo.pop(); if(node is not None) { print node.value; if(node.right is not None) { lifo.push(node.right); } if(node.left is not None) { lifo.push(node.left); } } }

For postorder traversal you simply swap the order you push the left and right subtrees onto the stack.

@Paolo: This is pre-order traversal, not in-order. Thanks for your reply, anyway :)

Collectives™ on Stack Overflow

Help me understand Inorder Traversal without using recursion

15 Answers 15

5 Comments

Comments

Comments

Comments

Comments

Comments

1 Comment

Comments

Comments

Comments

1 Comment

Comments

Comments

Comments

1 Comment

Linked

Hot Network Questions

Collectives™ on Stack Overflow

15 Answers 15

5 Comments

Comments

Comments

Comments

Comments

Comments

1 Comment

Comments

Comments

Comments

1 Comment

Comments

Comments

Comments

1 Comment

Linked

Related