DSA Tree Traversal

Tree traversal means visiting every node of a tree in a planned order. Different orders suit different jobs. Four common orders exist: preorder, inorder, postorder, and level order. Each one answers a different question about the tree.

Think about reading a family tree. You can start with the oldest ancestor and move down each branch. You can read all grandparents before parents. You can start from the youngest and move upward. Each reading order reveals different details, and the same logic applies to tree data.

The Sample Tree

          1
        /   \
       2     3
      / \
     4   5

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

Depth-First Traversals

Depth-first orders dive down a branch before visiting the neighbors. Three variations differ only in when the program visits the current node.

Preorder: Node, Left, Right

The program visits the node first and the children afterward. Copying a tree uses this order.

def preorder(node):
    if node:
        print(node.value, end=" ")
        preorder(node.left)
        preorder(node.right)

preorder(root)   # 1 2 4 5 3

Inorder: Left, Node, Right

The program visits the left side, the node, and the right side in that order. A binary search tree prints sorted values with this order.

def inorder(node):
    if node:
        inorder(node.left)
        print(node.value, end=" ")
        inorder(node.right)

inorder(root)   # 4 2 5 1 3

Postorder: Left, Right, Node

The program visits both children before the node. Deleting a tree uses this order, because every child must disappear before its parent.

def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.value, end=" ")

postorder(root)   # 4 5 2 3 1

Memory Trick

The word in the name tells where the node goes. Pre means before the children. In means between the children. Post means after the children.

Preorder  : [N] L R
Inorder   : L [N] R
Postorder : L R [N]

Breadth-First Traversal: Level Order

Level order visits the tree row by row, from top to bottom and left to right. A queue drives the process.

from collections import deque

def level_order(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        node = queue.popleft()
        result.append(node.value)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

print(level_order(root))   # [1, 2, 3, 4, 5]

Level 0:  1
Level 1:  2  3
Level 2:  4  5

Queue: [1] -> [2, 3] -> [3, 4, 5] -> [4, 5] -> [5] -> []

Which Order Fits Which Job

• Preorder copies a tree or saves its structure.
• Inorder returns sorted values from a binary search tree.
• Postorder deletes a tree or calculates sizes from the bottom up.
• Level order finds the shortest path to a node or prints a tree by rows.

Example: Tree Height

Postorder thinking computes height cleanly, since each node needs its children's heights first.

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

print(height(root))   # 3

Recursion Behind the Scenes

Every recursive call waits on the call stack until its children finish. The stack depth matches the tree height, so a balanced tree uses little memory while a long chain uses a lot. Writing the traversal with your own stack object gives the same visit order and avoids the recursion limit.

Real-Life Uses

File explorers walk folder trees to compute folder sizes, which relies on postorder logic. Expression calculators evaluate formulas stored as trees. Web browsers walk the page structure to draw each element. Company charts print level by level to show management layers.

Common Mistakes

Mixing up the three depth-first orders happens often. Trace the sample tree by hand and compare with the outputs above. Forgetting the empty-node check crashes the program on leaf nodes. Deep trees can overflow the recursion limit, and an explicit stack avoids that problem.

Complexity Summary

• Time: O(n), since each node is visited once.
• Space: O(h) for depth-first orders, where h is the tree height.
• Space for level order: O(w), where w is the widest row.

Key Points

• Traversal visits every node once in a set order.
• Preorder, inorder, and postorder differ by when the node gets visited.
• Level order uses a queue and moves row by row.
• Inorder on a binary search tree gives sorted output.
• Each traversal runs in O(n) time.