Search⌘ K
AI Features
Home
Courses
Coderust: Hacking the Coding Interview

Iterative In-order Traversal of Binary Tree

Explore the iterative in-order traversal method for binary trees using a stack. Understand the step-by-step process of visiting nodes in left, node, right sequence and analyze the algorithm’s time and space complexities. This lesson equips you to implement and trace in-order traversal without recursion on any binary tree.

We'll cover the following...

Statement

Given a binary tree, write an iterative algorithm for the in-order traversal of a binary tree. The algorithm should print out the value of each node such that it conforms to the in-order traversal of the input binary tree. The function is not expected to return a value, only to print it out on the console.

Example

Let’s look at the tree below:

G root 100 node1 50 root->node1 node2 200 root->node2 node3 25 node1->node3 node4 75 node1->node4 node7 35 node3->node7

The in-order traversal of the above tree produces the following output: 25, 35, 50, 75, 100, 200.

Sample input

The input list below represents the level-order traversal of the binary tree:

[100, 50, 200, 25, 75, 35]

Expected output

The sequence below represents the in-order traversal of the binary tree:

25, 35, 50, 75, 100, 200

Try it yourself

Note: The binary tree node’s class has members ...