1. Concept library
  2. Data Structures & Algorithms
  3. Module 9: Trees

Concept

Tree traversals

Preorder, inorder and postorder visit a tree's nodes in different orders, and breadth-first visits level by level. Which one you need follows from what the problem asks: copy, sort, delete or print by depth.

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

  1. Explain the order in which preorder, inorder and postorder visit nodes
  2. Write a level-order traversal with a queue
  3. Choose the traversal for copying, sorting, deleting or printing by depth

In practice

A few lines that show Tree traversals doing its job.

Python
from collections import deque

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

def by_level(root):
    levels, queue = [], deque([root] if root else [])
    while queue:
        levels.append([n.value for n in queue])
        queue = deque(c for n in queue for c in (n.left, n.right) if c)
    return levels

The common mistake

Watch for

Using recursion for level order. Depth-first recursion naturally goes down before across; level order needs a queue, and faking it with recursion needs an extra depth parameter and a second pass.

What to know first

Your roadmap puts these before Tree traversals, unless you already know them.

How it stays learned

Once a session shows you understand Tree traversals, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

  1. Day 3First recall, while it is fresh
  2. Day 7Second, a week on
  3. Day 18Last, when it has settled

Where it leads

Topics that build on Tree traversals.

Next in the moduleBinary search trees →