Binary Trees and Traversals

What is a binary tree?

A tree is made of nodes connected like a family tree, but upside down: one node at the top, the root, and every other node has exactly one parent above it. In a binary tree, each node has at most two children, called left and right. A node with no children is a leaf.

        1          ← root
      /   \
     2     3
    / \     \
   4   5     6     ← 4, 5 and 6 are leaves

A few words you'll meet everywhere:

• The depth of a node is how many steps it is from the root (the root has depth 0).
• The height of a tree is the number of nodes on the longest path from the root down to a leaf. The tree above has height 3.
• A subtree is any node together with everything below it. Node 2's subtree is {2, 4, 5}.

Trees model anything hierarchical: folders on your computer, the HTML of a web page, a company's reporting structure, or the moves in a game of noughts and crosses.

The key idea: trees are recursive

Every child of a node is the root of a smaller tree. So almost every tree problem can be solved by asking the same question about the left and right subtrees and combining the answers:

• Height = 1 + the larger of the two subtree heights (an empty tree has height 0).
• Number of nodes = 1 + nodes on the left + nodes on the right.
• Is value x in the tree? = it's this node, or it's on the left, or it's on the right.

Each of these visits every node once, so they are O(n). The recursion goes as deep as the tree is tall, so they use O(h) stack space, where h is the height.

Four ways to walk a tree

A traversal visits every node once. The three depth-first orders differ only in when you handle the node itself:

Level-order is different: it uses a queue instead of recursion. Take a node from the front, then add its children to the back. Processing exactly len(queue) nodes at a time gives you one level per round.

Building one yourself

The program builds the tree above by hand, walks it in all four orders, and computes its height and node counts recursively. It also includes build, which creates a tree from a level-order list with null for missing children: [1, 2, 3, 4, 5, null, 6]. That is the format the lab's tree problems use.

from collections import deque


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


def preorder(node, out):
    if node is None:
        return
    out.append(node.value)       # node, then left, then right
    preorder(node.left, out)
    preorder(node.right, out)


def inorder(node, out):
    if node is None:
        return
    inorder(node.left, out)      # left, then node, then right
    out.append(node.value)
    inorder(node.right, out)


def postorder(node, out):
    if node is None:
        return
    postorder(node.left, out)    # left, then right, then node
    postorder(node.right, out)
    out.append(node.value)


def level_order(root):
    levels, queue = [], deque([root] if root else [])
    while queue:
        level = []
        for _ in range(len(queue)):  # exactly the nodes on this level
            node = queue.popleft()
            level.append(node.value)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        levels.append(level)
    return levels


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


def count_nodes(node):
    return 0 if node is None else 1 + count_nodes(node.left) + count_nodes(node.right)


def count_leaves(node):
    if node is None:
        return 0
    if node.left is None and node.right is None:
        return 1
    return count_leaves(node.left) + count_leaves(node.right)


def build(values):
    """Build a tree from level-order values, where None marks a missing child."""
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue, i = deque([root]), 1
    while queue and i < len(values):
        node = queue.popleft()
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root


def joined(values):
    return " ".join(str(v) for v in values)


#        1
#      /   \
#     2     3
#    / \     \
#   4   5     6
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))

for name, walk in (("pre-order", preorder), ("in-order", inorder), ("post-order", postorder)):
    out = []
    walk(root, out)
    print(f"{name}: {joined(out)}")
print("level order:", " ".join("[" + ", ".join(map(str, level)) + "]" for level in level_order(root)))
print("height:", height(root))
print(f"nodes: {count_nodes(root)}, leaves: {count_leaves(root)}")

copy = build([1, 2, 3, 4, 5, None, 6])
out = []
inorder(copy, out)
print("built from [1, 2, 3, 4, 5, null, 6], in-order:", joined(out))

pre-order: 1 2 4 5 3 6
in-order: 4 2 5 1 3 6
post-order: 4 5 2 6 3 1
level order: [1] [2, 3] [4, 5, 6]
height: 3
nodes: 6, leaves: 3
built from [1, 2, 3, 4, 5, null, 6], in-order: 4 2 5 1 3 6

Balanced and unbalanced trees

How fast tree operations are depends on the height. A balanced tree with n nodes has height about log₂ n: a million nodes fit in about 20 levels. But if every node only has a right child, the "tree" is really a linked list with height n. Recursive code on such a tree can even crash with a stack overflow. Self-balancing trees (AVL trees and red-black trees) rearrange themselves after every insert to keep the height O(log n).

Trees in the standard libraries

None of the four languages has a general-purpose binary tree type, because the right shape depends on the problem. You write a small node class like the one above. What the libraries do provide are balanced search trees built on this idea: TreeMap/TreeSet in Java and std::map/std::set in C++. Python and JavaScript have none built in. The Binary search trees guide covers how they work.

Common mistakes

• Forgetting the base case. Every recursive tree function must handle the empty tree (null) first.
• Mixing up height and depth, or counting edges in one place and nodes in another. Decide on one definition and stick to it.
• Reading len(queue) inside the level loop. Read it once before the loop; it changes as children are added.
• Deep recursion on skewed trees. For trees that may be very deep, use an explicit stack or a queue instead of recursion.

When to use a tree

Use a tree when your data is hierarchical, or when you want a structure that stays sorted as you insert and delete (a binary search tree). Many problems that don't look like trees, such as exploring choices or splitting a problem in half, turn into tree-shaped recursion.