Lesson 7 of 14

Trees and Traversal

Folders contain files and other folders. A tree represents such a hierarchy. Here we use a rooted tree, with one starting node and parent-child relationships.

Essential terms

• Root: The starting node at the top.
• Parent and child: Directly connected nodes above and below one another. Every non-root node has one parent.
• Leaf: A node without children.
• Binary tree: Each node has at most two children, distinguished as left and right.

This tree has five nodes. A is the root; C, D, and E are leaves.

    A
   / \
  B   C
 / \
D   E

When do you visit the current node?

Traversal means visiting every node. If we explore left children first, these are the resulting orders:

• Preorder: Self → left → right: A B D E C.
• Inorder: Left → self → right: D B E A C.
• Postorder: Left → right → self: D E B C A.
• Level order: Visit nearby levels first using a queue: A B C D E.

Follow an inorder traversal

A tuple (value, left, right) represents one node. None means a child is absent.

tree = ("A",
        ("B", ("D", None, None), ("E", None, None)),
        ("C", None, None))

def inorder(node):
    if node is None:
        return
    value, left, right = node
    inorder(left)
    print(value)
    inorder(right)

inorder(tree)

The output is D, B, E, A, then C. The function processes A’s left subtree before printing A. Visiting every node once takes O(n) time. Recursive call space is O(h), where h is the tree’s height.

Check your understanding

You need to calculate each subfolder’s size before adding them into a parent folder’s total. Which fits better: preorder or postorder?