Data Structures · Lesson 5 of 8

Trees

Binary trees, traversals, and binary search trees.

• Intermediate
• 16 min read
• 3 objectives

Before this lessonLesson 4: Stacks and Queues

A tree is a hierarchy: one root node at the top, and every node may have children below it. Nodes with no children are leaves. Folders on your disk, the HTML DOM and organization charts are all trees. A binary tree limits each node to at most two children, called left and right.

Data that branches

Lists and arrays are lines. Many things in the real world are not lines: a folder contains folders that contain files, an organisation chart branches from a CEO, a web page's HTML nests elements inside elements. A tree models this. It has one root at the top, each node can have children, and there are no loops. Trees appear everywhere: file systems, the DOM, databases, compilers and search.

Vocabulary

• Depth of a node: number of edges from the root.
• Height of the tree: the longest path from the root down to a leaf.
• Subtree: any node together with all of its descendants. Trees are recursive by nature.

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

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

Depth-first traversal

Recursion fits trees perfectly: handle the node, then hand the left and right subtrees to the same function. The three orders differ only in when the node is visited. In-order is left, node, right.

def inorder(node):
    if not node:
        return
    inorder(node.left)
    print(node.val)
    inorder(node.right)

inorder(root)

1
2
3
4
6

Pre-order (node, left, right) is useful for copying a tree. Post-order (left, right, node) is useful for deleting one, since children are processed before their parent.

Breadth-first (level order)

Visit nodes level by level using a queue.

from collections import deque

def level_order(root):
    result, q = [], deque([root])
    while q:
        node = q.popleft()
        result.append(node.val)
        if node.left:  q.append(node.left)
        if node.right: q.append(node.right)
    return result

print(level_order(root))

[4, 2, 6, 1, 3]

Binary search trees

A binary search tree (BST) keeps every left descendant smaller and every right descendant larger than the node. Searching is like binary search: at each node, go left or right, discarding half the remaining tree. That is O(log n) when the tree is balanced, but degrades to O(n) if it becomes a long chain. In-order traversal of a BST visits values in sorted order, as you saw above.

def contains(node, target):
    while node:
        if target == node.val:
            return True
        node = node.left if target < node.val else node.right
    return False

print(contains(root, 3), contains(root, 5))

True False

Building a small tree and walking it

class Node:
    def __init__(self, value):
        self.value = value
        self.children = []

root = Node("projects")
site = Node("site"); notes = Node("notes")
root.children += [site, notes]
site.children += [Node("index.html"), Node("style.css")]
notes.children.append(Node("todo.txt"))

def show(node, depth=0):
    print("  " * depth + node.value)
    for child in node.children:
        show(child, depth + 1)

show(root)

projects
  site
    index.html
    style.css
  notes
    todo.txt

Notice the function calls itself on each child. Trees and recursion are natural partners: a tree is either empty or a node with smaller trees beneath it.

Binary search tree: sorted and fast to search

In a binary search tree, everything in a node's left subtree is smaller and everything in its right subtree is larger. Searching therefore discards half of the remaining tree at every step, exactly like binary search on a sorted list.

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

    def insert(self, v):
        if v < self.value:
            if self.left: self.left.insert(v)
            else: self.left = BST(v)
        else:
            if self.right: self.right.insert(v)
            else: self.right = BST(v)

    def contains(self, v):
        if v == self.value: return True
        side = self.left if v < self.value else self.right
        return bool(side) and side.contains(v)

    def in_order(self):
        return (self.left.in_order() if self.left else []) + [self.value] + (self.right.in_order() if self.right else [])

t = BST(8)
for n in [3, 10, 1, 6, 14, 4]:
    t.insert(n)

print(t.in_order())
print(t.contains(6), t.contains(7))

[1, 3, 4, 6, 8, 10, 14]
True False

An in-order walk of a binary search tree visits values in sorted order, which is a neat way to see that the structure is doing its job.

Height decides speed

Search cost is proportional to the tree's height. A balanced tree with a million nodes is only about 20 levels tall. A degenerate tree (inserting already-sorted numbers) becomes a long chain of height a million, no better than a linked list. Real databases use self-balancing trees to guarantee good height.

Key takeaways

• A tree has a root, parent-child links and no cycles; it models hierarchies.
• Recursion is the natural way to process trees.
• In a binary search tree, left is smaller and right is larger, giving O(log n) search when balanced.
• In-order traversal of a BST yields sorted values.

# Write your solution here