Tree Traversals

Analogy categoryAnalogies

Introduction

Tree traversal is the process of visiting every node in a tree exactly once in a systematic order. There are two broad families: depth-first traversals (inorder, preorder, postorder), which recursively explore as far as possible along each branch before backtracking, and breadth-first traversal (level-order), which visits nodes level by level using a queue. The choice of traversal matters: inorder traversal of a BST yields sorted output, preorder is useful for copying/serializing a tree, postorder is used for safely deleting a tree or evaluating expression trees, and level-order is used for shortest-path-style processing and printing a tree level by level.

🏏

Cricket analogy: Visiting every player in a squad hierarchy is like a tree traversal: depth-first drills go deep into one fielding unit before backtracking, while level-order calls out players row by row on the team photo, useful for printing the squad list rank by rank.

Structure/Syntax

python

from collections import deque

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

def inorder(node, out):
    if node:
        inorder(node.left, out)
        out.append(node.value)
        inorder(node.right, out)

def preorder(node, out):
    if node:
        out.append(node.value)
        preorder(node.left, out)
        preorder(node.right, out)

def postorder(node, out):
    if node:
        postorder(node.left, out)
        postorder(node.right, out)
        out.append(node.value)

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

Explanation

Inorder visits left subtree, then the node, then right subtree (Left-Node-Right) — on a BST this always produces values in ascending sorted order. Preorder visits the node first, then left, then right (Node-Left-Right) — useful for creating a copy of the tree because you record the root before its children. Postorder visits left, then right, then the node (Left-Right-Node) — useful for deleting a tree bottom-up or evaluating an expression tree, since children are fully processed before their parent. Level-order (breadth-first) uses a queue instead of recursion: it processes the root, then enqueues its children, and repeats, visiting the tree level by level, left to right.

🏏

Cricket analogy: Inorder (left-node-right) walking a BST of player rankings yields them sorted ascending, like reading a batting average list low to high; preorder records the captain before the squad, useful for copying a team sheet; postorder finalizes support staff before the captain, useful for disbanding a squad; level-order calls out the whole XI row by row using a queue.

Example

python

#         5
#        / \
#       3   8
#      / \   \
#     1   4   9
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
root.right.right = TreeNode(9)

result = []
inorder(root, result)
print("inorder:", result)

result = []
preorder(root, result)
print("preorder:", result)

result = []
postorder(root, result)
print("postorder:", result)

print("level-order:", level_order(root))

Output

For the tree shown above, the traversals produce: inorder -> [1, 3, 4, 5, 8, 9] (sorted, since this is a BST); preorder -> [5, 3, 1, 4, 8, 9] (root first, then left subtree, then right subtree); postorder -> [1, 4, 3, 9, 8, 5] (children before parent, root last); level-order -> [5, 3, 8, 1, 4, 9] (visited level by level, top to bottom, left to right). Each depth-first traversal runs in O(n) time and O(h) space (recursion stack), while level-order also runs in O(n) time but uses O(w) space where w is the maximum width of the tree (up to O(n) for a wide tree).

🏏

Cricket analogy: For a squad-ranking tree, inorder gives sorted batting averages, preorder gives captain-first order, postorder gives support-staff-first order, and level-order gives row-by-row squad photo order; each depth-first walk takes O(n) time and O(h) stack space for the squad depth h, while level-order takes O(n) time and O(w) space for the widest row w.

Key Takeaways

Inorder (Left-Node-Right) yields sorted output on a BST.
Preorder (Node-Left-Right) is ideal for copying or serializing a tree.
Postorder (Left-Right-Node) is ideal for safe deletion or expression evaluation.
Level-order (breadth-first) uses a queue and visits nodes top-to-bottom, left-to-right.
All traversals are O(n) time; DFS uses O(h) space, BFS uses up to O(n) space.

Practice what you learned

1. Which traversal order visits a BST's nodes in sorted ascending order?

2. Which data structure is typically used to implement level-order (breadth-first) traversal?

3. For the tree with root 5, left child 3, right child 8 (and 3 has children 1, 4; 8 has right child 9), what is the postorder traversal?

4. What is the space complexity of a recursive preorder traversal in the worst case (a completely skewed tree)?

Was this page helpful?

Binary Search Trees

AVL Trees

Topics covered

#Python#DataStructuresStudyNotes#DataStructures#TreeTraversals#Tree#Traversals#Structure#Syntax#StudyNotes#SkillVeris