Tree Data Structure: Traversals

Tree Traversals

Tree traversal means visiting each node in a specific order.

Two main categories:

Depth-First Search (DFS) → Preorder, Inorder, Postorder
Breadth-First Search (BFS) → Level-order

We’ll use this basic class written in Python for examples:

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

Preorder Traversal (Root → Left → Right)

       A
      / \
     B   C
    / \
   D   E

Preorder: A → B → D → E → C

# Recursive
def preorder(node):
    if not node:
        return
    print(node.val)      # Root
    preorder(node.left)  # Left
    preorder(node.right) # Right

# Iterative
def preorder_iter(root):
    if not root:
        return
    stack = [root]
    while stack:
        node = stack.pop()
        print(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

Inorder Traversal (Left → Root → Right)

       A
      / \
     B   C
    / \
   D   E

Inorder: D → B → E → A → C

# Recursive
def preorder(node):
    if not node:
        return
    print(node.val)      # Root
    preorder(node.left)  # Left
    preorder(node.right) # Right

# Iterative
def preorder_iter(root):
    if not root:
        return
    stack = [root]
    while stack:
        node = stack.pop()
        print(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

Postorder Traversal (Left → Right → Root)

       A
      / \
     B   C
    / \
   D   E

Postorder: D → E → B → C → A

# Recursive
def postorder(node):
    if not node:
        return
    postorder(node.left)   # Left
    postorder(node.right)  # Right
    print(node.val)        # Root

# Iterative
def postorder_iter(root):
    if not root:
        return
    stack, out = [root], []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    for val in reversed(out):
        print(val)

Level Order Traversal

       A
      / \
     B   C
    / \
   D   E

Level Order: A → B → C → D → E

from collections import deque

def level_order(root):
    if not root:
        return
    q = deque([root])
    while q:
        node = q.popleft()
        print(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

Grouped Level Order

Visit nodes level by level, left → right.
Group nodes per level.

        A
       / \
      B   C
     / \   \
    D   E   F

Level 1: [A]             -> Start with root
Level 2: [B, C]          -> Children of A
Level 3: [D, E, F]       -> Children of B and C

Output: [[A], [B, C], [D, E, F]]

def level_order_grouped(root):
    res = []
    if not root:
        return res
    q = deque([root])
    while q:
        size = len(q)
        level = []
        for _ in range(size):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        res.append(level)
    return res

Zigzag Level Order

Visit nodes level by level, but alternate the order each level: left→right, right→left, left→right..

        A
       / \
      B   C
     / \   \
    D   E   F

Level 1 (Left→Right):  [A]
Level 2 (Right→Left):  [C, B]
Level 3 (Left→Right):  [D, E, F]

Output: [[A], [C, B], [D, E, F]]

def zigzag_level_order(root):
    res = []
    if not root:
        return res
    q = deque([root])
    left_to_right = True
    while q:
        size = len(q)
        level = deque()
        for _ in range(size):
            node = q.popleft()
            if left_to_right:
                level.append(node.val)
            else:
                level.appendleft(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        res.append(list(level))
        left_to_right = not left_to_right
    return res

# Tree Data Structure: Traversals