Inorder Traversal of a Binary Tree using Iteration

Algorithm Steps

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

Inorder Traversal of a Binary Tree using Iteration - Code Examples Code

Python

Java

JavaScript

C++

Kotlin

Swift

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