Lab 2 — Trees & Binary Trees in Python

Before you start

A binary tree is either the empty tree None, or a list with three items t = [key, left, right], where left and right are themselves binary trees.

For instance, the tree with root 1 and two leaf children 2 and 3 is [1, [2, None, None], [3, None, None]].

This matches the inductive definition from the lesson — so every function in this lab is naturally a recursive function whose base case is None. As in Lab 1, networkx is used only to draw the trees and check the work.

Run the notebook from top to bottom. Replace each # TODO and remove the raise NotImplementedError. A printed ✔ means the exercise's tests pass.

Size, height, leaves
The three depth-first traversals + level-order
Rebuilding a tree from two traversals
Binary search trees
Expression trees
A tree is a special graph

Setup

Run this cell first. It provides leaf and the tree-drawing helper.

Python · provided

import networkx as nx
import matplotlib.pyplot as plt
from collections import deque

def leaf(key):
    """A leaf: a node with two empty subtrees."""
    return [key, None, None]

def draw_btree(t, title=""):
    """Draw a binary tree given in [key, left, right] form."""
    if t is None:
        print("(empty tree)")
        return
    pos, labels, edges, counter = {}, {}, [], {"x": 0, "id": 0}

    def walk(node, depth):
        nid = counter["id"]; counter["id"] += 1
        key, left, right = node
        lid = walk(left, depth + 1) if left is not None else None
        pos[nid] = (counter["x"], -depth); counter["x"] += 1   # x = in-order rank
        labels[nid] = str(key)
        rid = walk(right, depth + 1) if right is not None else None
        for child in (lid, rid):
            if child is not None:
                edges.append((nid, child))
        return nid

    walk(t, 0)
    H = nx.Graph(); H.add_nodes_from(pos); H.add_edges_from(edges)
    plt.figure(figsize=(max(4, len(pos) * 0.55), 3.5))
    nx.draw(H, pos, labels=labels, with_labels=True, node_color="#ffd28f",
            node_size=650, font_weight="bold", edge_color="#666666")
    plt.title(title)
    plt.show()

print("Setup OK — networkx", nx.__version__)

Exercise 1Size, height, leaves

The cell below builds a first tree t1 and draws it — keep that picture in mind for the whole lab. Then implement, recursively:

size(t) — number of nodes (size(None) == 0);
height(t) — height of the tree, with the convention height(None) == -1 (so a single node has height 0);
count_leaves(t) — number of leaves.

The test cell also checks two inequalities from the lesson: $$\text{leaves}(t) \le 2^{h(t)} \qquad\text{and}\qquad \text{size}(t) \le 2^{h(t)+1} - 1.$$

Python · provided

t1 = [8,
      [4, leaf(2), leaf(6)],
      [12, [10, leaf(9), None], leaf(14)]]
draw_btree(t1, "t1")

Python · your turn

def size(t):
    """Number of nodes of t."""
    # TODO
    raise NotImplementedError

def height(t):
    """Height of t, with height(None) == -1."""
    # TODO
    raise NotImplementedError

def count_leaves(t):
    """Number of leaves of t."""
    # TODO — careful: three cases (empty, leaf, internal node)
    raise NotImplementedError

Test cell

assert size(None) == 0 and size(leaf(7)) == 1 and size(t1) == 8
assert height(None) == -1 and height(leaf(7)) == 0 and height(t1) == 3
assert count_leaves(None) == 0 and count_leaves(t1) == 4
assert count_leaves(t1) <= 2 ** height(t1)
assert size(t1) <= 2 ** (height(t1) + 1) - 1
print("Exercise 1 ✔")

Exercise 2Traversals

Implement the three depth-first traversals, each returning the list of keys:

preorder(t) — root, then left subtree, then right subtree;
inorder(t) — left subtree, then root, then right subtree;
postorder(t) — left subtree, then right subtree, then root;
level_order(t) — top to bottom, left to right, using a queue exactly like BFS in Lab 1.

Python · your turn

def preorder(t):
    """Keys of t in preorder (root, left, right)."""
    # TODO
    raise NotImplementedError

def inorder(t):
    """Keys of t in inorder (left, root, right)."""
    # TODO
    raise NotImplementedError

def postorder(t):
    """Keys of t in postorder (left, right, root)."""
    # TODO
    raise NotImplementedError

def level_order(t):
    """Keys of t level by level (a queue of subtrees, as in BFS)."""
    # TODO
    raise NotImplementedError

Test cell

assert preorder(t1)    == [8, 4, 2, 6, 12, 10, 9, 14]
assert inorder(t1)     == [2, 4, 6, 8, 9, 10, 12, 14]
assert postorder(t1)   == [2, 6, 4, 9, 10, 14, 12, 8]
assert level_order(t1) == [8, 4, 12, 2, 6, 10, 14, 9]
print("Exercise 2 ✔  (the inorder list came out sorted — why? see Exercise 4!)")

Exercise 3Rebuilding a tree from two traversals

One traversal alone does not determine a binary tree (the test cell exhibits two different trees with the same preorder). But the pair (preorder, inorder) does, when all keys are distinct:

the first key of pre is the root;
find it in ino: everything to its left is the inorder of the left subtree, everything to its right the inorder of the right subtree;
split pre accordingly and recurse.

Python · your turn

def rebuild(pre, ino):
    """The unique binary tree whose preorder is `pre` and inorder is `ino`."""
    # TODO — base case: empty lists; then split and recurse
    raise NotImplementedError

Test cell

assert rebuild(preorder(t1), inorder(t1)) == t1

# two different trees sharing the same preorder:
ta = [1, leaf(2), None]
tb = [1, None, leaf(2)]
assert preorder(ta) == preorder(tb) and ta != tb
print("Exercise 3 ✔")
draw_btree(rebuild(preorder(t1), inorder(t1)), "t1, rebuilt from (preorder, inorder)")

Exercise 4Binary search trees

In a binary search tree (BST), every key in the left subtree is smaller than the root's key, every key in the right subtree is larger — at every node.

bst_insert(t, k) — return the BST with k inserted (build new nodes along the insertion path; ignore duplicates);
bst_search(t, k) — True iff k appears, visiting one branch only (never both);
bst_from(values) — fold bst_insert over a list;
is_bst(t) — check the BST property. Hint: one single line, using a traversal from Exercise 2.

Python · your turn

def bst_insert(t, k):
    """The BST t with key k inserted (duplicates ignored)."""
    # TODO
    raise NotImplementedError

def bst_search(t, k):
    """True iff k is a key of the BST t (visit a single branch)."""
    # TODO
    raise NotImplementedError

def bst_from(values):
    """BST obtained by inserting the values in order."""
    # TODO
    raise NotImplementedError

def is_bst(t):
    """True iff t satisfies the BST property."""
    # TODO — one line!
    raise NotImplementedError

Test cell

import random
random.seed(1)
values = random.sample(range(100), 15)

B = bst_from(values)
assert is_bst(B) and is_bst(t1)
assert inorder(B) == sorted(values)            # inorder of a BST is sorted!
assert all(bst_search(B, v) for v in values)
assert not bst_search(B, 101)
assert not is_bst([5, leaf(9), leaf(1)])

worst = bst_from(sorted(values))               # sorted insertion order...
assert height(worst) == len(values) - 1        # ...gives a degenerate 'spaghetti' BST
print("Exercise 4 ✔  height:", height(B), "(random order) vs",
      height(worst), "(sorted order)")
draw_btree(B, "BST, random insertion order")
draw_btree(worst, "BST, sorted insertion order — degenerate")

Exercise 5Expression trees

An arithmetic expression is a binary tree whose leaves hold numbers and whose internal nodes hold operators — e.g. (3 + 4) * (5 - 2).

eval_tree(t) — the value of the expression;
to_infix(t) — a fully parenthesized string such as "((3+4)*(5-2))";
from_postfix(tokens) — build the tree from postfix (reverse Polish) notation using a stack: push a leaf for each number; for an operator, pop the right then the left operand and push the new node.

Notice how the three functions are really the traversals of Exercise 2 in disguise: postfix is the postorder, the infix string follows the inorder, and evaluation is a bottom-up (postorder) computation.

Python · your turn

OPS = {"+": lambda a, b: a + b, "-": lambda a, b: a - b,
       "*": lambda a, b: a * b, "/": lambda a, b: a / b}

def eval_tree(t):
    """Value of the expression tree t."""
    # TODO — a leaf holds its value; an internal node applies OPS[t[0]]
    raise NotImplementedError

def to_infix(t):
    """Fully parenthesized infix string of t."""
    # TODO
    raise NotImplementedError

def from_postfix(tokens):
    """Expression tree of a postfix token list, via a stack."""
    # TODO
    raise NotImplementedError

Test cell

e = ["*", ["+", leaf(3), leaf(4)], ["-", leaf(5), leaf(2)]]
assert eval_tree(e) == 21
assert to_infix(e) == "((3+4)*(5-2))"

e2 = from_postfix([3, 4, "+", 5, 2, "-", "*"])
assert e2 == e
assert postorder(e) == [3, 4, "+", 5, 2, "-", "*"]   # postfix IS the postorder

e3 = from_postfix([1, 2, 3, "*", "+", 4, "-"])       # 1 + 2*3 - 4
assert eval_tree(e3) == 3 and to_infix(e3) == "((1+(2*3))-4)"
print("Exercise 5 ✔")
draw_btree(e, "(3+4)*(5-2)")

Exercise 6A tree is a special graph

The lesson ended on the bridge between the two worlds: a tree is exactly a connected acyclic graph, and then $|E| = |V| - 1$.

Implement btree_to_graph(t): convert a binary tree into a dict-of-lists graph as in Lab 1 — vertices are the keys (assumed distinct), edges are the parent–child links, undirected and with no left/right distinction. The test cell then verifies the characterization on t1 with networkx as referee.

Python · your turn

def btree_to_graph(t):
    """Undirected dict-of-lists graph of the parent-child edges of t."""
    # TODO — walk the tree; for each child, add the edge in both directions
    raise NotImplementedError

Test cell

Gt = btree_to_graph(t1)
H = nx.Graph()
H.add_nodes_from(Gt)
H.add_edges_from((u, v) for u in Gt for v in Gt[u])

assert set(Gt) == set(preorder(t1))                    # same vertices as keys
assert nx.is_connected(H) and nx.is_tree(H)            # connected + acyclic
assert sum(len(Gt[u]) for u in Gt) // 2 == len(Gt) - 1 # |E| = |V| - 1
print("Exercise 6 ✔ — t1 is a tree in the graph sense too")

plt.figure(figsize=(5, 4))
nx.draw(H, nx.spring_layout(H, seed=3), with_labels=True,
        node_color="#a8dadc", node_size=650, font_weight="bold",
        edge_color="#666666")
plt.title("t1 as a plain graph — the root is no longer special!")
plt.show()

Summary

On the [key, left, right] representation you implemented: size / height / leaf count, the four classical traversals, reconstruction from (preorder, inorder), binary search trees (insertion, search, the sorted-inorder characterization, degenerate shapes), expression trees (evaluation, infix printing, postfix parsing) — and finally crossed the bridge back to Lab 1 by checking that a tree really is a connected acyclic graph with $|V| - 1$ edges.

Lab 2 — Trees & Binary Trees in Python

Before you start

Contents

Setup

Exercise 1Size, height, leaves

Exercise 2Traversals

Exercise 3Rebuilding a tree from two traversals

Exercise 4Binary search trees

Exercise 5Expression trees

Exercise 6A tree is a special graph

Summary