Inorder Traversal of a Binary Tree using Iteration

Contents

ProblemExamplesVisualizationSolutionAlgorithmCode

Problem Statement❯

You are given the root of a binary tree. Your task is to perform an inorder traversal (left → root → right) of the tree using an iterative approach and return the list of visited node values. Unlike the recursive approach, this solution should avoid using function call stack and instead simulate the process using an explicit stack data structure.

Examples❯

Input Tree Inorder Traversal Output Description
[1, 2, 3, 4, 5, null, 6]
[4, 2, 5, 1, 3, 6] Standard case: Tree with both left and right children and missing node
[1]
[1] Edge case: Tree with a single node
[] [] Edge case: Empty tree with no nodes
[1, 2, null, 3, null, null, null, 4]
[4, 3, 2, 1] Edge case: Deep left-skewed tree
[1, null, 2, null, null, null, 3]
[1, 2, 3] Edge case: Deep right-skewed tree
[5, 3, 7, 2, 4, 6, 8]
[2, 3, 4, 5, 6, 7, 8] Balanced binary search tree (BST): inorder gives sorted values

Visualization Player

Solution❯

Normal Case

In a typical binary tree, nodes can have both left and right children. The inorder traversal visits the left subtree first, then the current node, and finally the right subtree. By using a stack, we simulate the recursive behavior. We push nodes while going left, then visit them, and move to the right child. This ensures we visit each node in the correct order.

Edge Case – Skewed Left Tree

In a left-skewed tree, all nodes only have a left child. As we traverse, we push each node onto the stack until we hit null. Then we start popping and visiting nodes in reverse order (bottom-up). The result is a list from the smallest to the largest value as seen in the tree.

Edge Case – Skewed Right Tree

In a right-skewed tree, each node has only a right child. Since there are no left nodes to push onto the stack, we visit each node, then move to the right. This results in visiting nodes in the same sequence as they appear from top to bottom.

Empty Tree

If the root node is null, then the tree is empty. In such a case, there are no nodes to visit, and the output should simply be an empty list. This case is important to handle to avoid null pointer errors in implementation.

Algorithm Steps❯

  1. Start with the root node of the binary tree.
  2. Initialize an empty stack and set the current node as the root.
  3. While the current node is not null or the stack is not empty, do:
  4.     Push the current node onto the stack and move to its left child until the current node is null.
  5. When the current node is null, pop a node from the stack, record its value, and set the current node to its right child.
  6. Repeat until both the current node is null and the stack is empty.

Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorderTraversal(root):
    result = []
    stack = []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
    return result

if __name__ == '__main__':
    # Construct binary tree:
    #        1
    #       / \
    #      2   3
    #     / \
    #    4   5
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print(inorderTraversal(root))