Trees

Trees as connected graphs with no cycles, rooted trees and their vocabulary, binary trees and typical uses.

A4.5Trees and graphsA level25 min

A tree is a special kind of graph, and one of the most used structures in computing. File systems, web pages, compilers, game-playing programs and fast searching are all built on trees. At GCSE you met trees informally, as decision trees or folder structures; at A level you need the precise definitions and the vocabulary that goes with them.

A tree is a graph

A tree is a connected, undirected graph with no cycles.

• Connected: there is a path between every pair of vertices.
• No cycles: you cannot leave a vertex and come back to it without retracing an edge.

Two facts follow from the definition.

• There is exactly one path between any two vertices. There is at least one because the tree is connected, and no more than one because two different paths between the same vertices would make a cycle.
• A tree with n vertices has exactly n - 1 edges. Remove any edge and it falls into two pieces; add any edge and it makes a cycle.

The tree above has no root and no top. Nothing in the definition needs one.

Rooted trees

A rooted tree is a tree in which one vertex has been designated as the root. Choosing a root gives every edge a direction, away from the root, and creates parent-child relationships. This rooted tree is the folders and files on the robot's memory card:

Every node except the root has exactly one parent, and every other node is a descendant of the root.

Where rooted trees are used

• File systems: folders contain files and other folders. A path such as /code/lib/motor.py is the one route from the root to that file.
• Web pages: HTML elements nest inside each other, and the browser holds the page as a tree, the Document Object Model.
• Compilers: source code is parsed into a syntax tree before code is generated from it.
• Expression trees: operators are internal nodes and numbers are leaves (lesson A4.7).
• Binary search trees: data kept in order so it can be searched quickly (next lesson).
• Decision trees in machine learning, and game trees that a game-playing program searches to choose its move.
• Huffman trees, which build the codes for Huffman compression.

A rooted tree in Python

A dictionary from each node to the list of its children stores a rooted tree. Recursion suits trees, because every child is the root of a smaller tree, its subtree:

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

CHILDREN = {"/": ["logs", "maps", "code"], "logs": ["mon.csv", "tue.csv"], "maps": ["mat.json"],
            "code": ["main.py", "lib"], "lib": ["motor.py", "sensor.py"]}

def show(node, depth):
    print("    " * depth + node)
    for child in CHILDREN.get(node, []):          # a leaf is not a key, so it gets []
        show(child, depth + 1)

def count(node):
    """The number of nodes in the subtree rooted at node."""
    total = 1
    for child in CHILDREN.get(node, []):
        total = total + count(child)
    return total

show("/", 0)
print("nodes:", count("/"))
print("nodes in the code subtree:", count("code"))

Run this in the simulator

Every recursive tree function has the same shape: deal with this node, then call itself on each child. A leaf has no children, so the loop does nothing and the recursion stops there: the leaf is the base case.

Is it a tree?

Given an undirected graph as a list of edges, you can test the definition directly. A graph with n vertices is a tree if it has exactly n - 1 edges and it is connected; together those two guarantee there is no cycle. Connectedness is checked with a traversal from the previous lessons:

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def is_tree(vertices, edges):
    if len(edges) != len(vertices) - 1:
        return False
    neighbours = {v: [] for v in vertices}
    for u, v in edges:
        neighbours[u].append(v)
        neighbours[v].append(u)
    reached = [vertices[0]]                       # traverse from any vertex
    stack = [vertices[0]]
    while len(stack) > 0:
        for n in neighbours[stack.pop()]:
            if n not in reached:
                reached.append(n)
                stack.append(n)
    return len(reached) == len(vertices)          # connected if it reached them all

V = ["P", "Q", "R", "S", "T", "U"]
print(is_tree(V, [("P", "R"), ("Q", "R"), ("R", "S"), ("S", "T"), ("S", "U")]))
print(is_tree(V, [("P", "R"), ("Q", "R"), ("R", "S"), ("S", "T"), ("T", "U"), ("U", "S")]))
print(is_tree(V, [("P", "R"), ("Q", "R"), ("S", "T"), ("T", "U"), ("U", "S")]))

Run this in the simulator

The first is the tree in the figure. The second has one edge too many, making the cycle S, T, U. The third has the right number of edges, but it still has that cycle and has lost the edge from R to S, so it is in two pieces and not connected.

Binary trees

A binary tree is a rooted tree in which each node has at most two children, called its left child and right child. The folder tree is not binary, because / has three children. Binary trees fill the next two lessons, because two children per node is exactly what a comparison with two outcomes needs. In code, each node holds its data and two pointers, one to each child:

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None          # None: no child on this side
        self.right = None

# a tiny decision tree: left for yes, right for no
root = Node("is the way clear?")
root.left = Node("drive forward")
root.right = Node("is the left clear?")
root.right.left = Node("turn left")
root.right.right = Node("turn right")

node = root
answers = [False, True]           # the way is not clear, the left is
for yes in answers:
    print(node.data, "yes" if yes else "no")
    node = node.left if yes else node.right
print("so:", node.data)

Run this in the simulator

Task: facts about a tree

TREE is a rooted tree stored as a dictionary: each key is a node that has children, and its value is the list of those children. Leaves appear only inside children lists, never as keys, and the keys are in no particular order, so the root is not necessarily first. Write a recursive function height(node) that returns the height of the subtree rooted at node, which is 0 for a leaf. Then print five lines: root: and the root; nodes: and the number of nodes; edges: and the number of edges; leaves: and every leaf in alphabetical order, separated by single spaces; and height: and the height of the whole tree. Work everything out from TREE.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

TREE = {
    "fetch": ["approach", "grip"],
    "mission": ["find", "fetch", "return"],
    "approach": ["align", "creep"],
    "find": ["scan", "turn"],
    "return": ["drive", "drop"],
}

def height(node):
    return 0

Challenges

1. Print every node of TREE with its depth, the root first.
2. Add one node to TREE so that its height becomes 4, and check your program agrees.
3. Write is_binary(tree) that returns True when no node in a tree stored like TREE has more than two children.