In-order Traversal

In-order traversal follows the "left, root, right" order. For each node, the algorithm recursively traverses the left subtree, then processes the node itself, and finally recursively traverses the right subtree. When used on a binary search tree, in-order traversal visits the nodes in ascending order, which is a very useful property.

In-Order Traversal (Tree)

Step 1 of 0

Action

Ready to start

Current Node

None

Call Stack

[]

Traversal Order

[]

Current Node

Visited

In Call Stack

Unvisited

Recursive In-order Traversal

The recursive implementation of in-order traversal is elegant and directly follows the "left, root, right" definition.

Algorithm Steps

Base Case: If the current node is `null`, return.
Go Left: Recursively call the in-order traversal function on the left child.
Visit Root: Process the current node (e.g., add its value to a list).
Go Right: Recursively call the in-order traversal function on the right child.

Recursive In-order Traversal


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder_traversal(root):
    result = []
    
    def dfs(node):
        if not node:
            return
        dfs(node.left)
        result.append(node.val)
        dfs(node.right)
    
    dfs(root)
    return result

Iterative In-order Traversal

The iterative approach uses a stack to mimic the behavior of recursion, providing a non-recursive way to perform the traversal. This can be useful for very deep trees where recursion might lead to a stack overflow.

Algorithm Steps

Initialization: Create an empty stack and set a `current` pointer to the root node.
Go Left: As long as the `current` node is not `null`, push it onto the stack and move `current` to its left child.
Visit Root: Once `current` is `null`, pop a node from the stack and process its value.
Go Right: Move the `current` pointer to the right child of the popped node.
Repeat: Continue until both the `current` pointer is `null` and the stack is empty.

Iterative In-order Traversal


import collections

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder_traversal_iterative(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