Binary trees

A list is a row: after each item comes one next item, and a loop walks along the row from the start to the end. Plenty of data isn't a row. A family tree, the folders on a computer and a tournament bracket all branch: one thing leads to two or more, and each of those leads on to more again. The simplest data that branches is a binary tree:

        8
       / \
      3   10
     / \    \
    1   6    14

Each value in it sits in a node. A node has a value and at most two children, a left one and a right one. The root is the node at the top, the one that all the others hang from, and the nodes without children are leaves: here 1, 6 and 14.

A tree needs only one class, for a node that knows its value and its two children. A missing child is None:

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

Since the children are parameters with default values, the whole tree above can be built by nesting the calls of the constructor:

tree = Node(8, Node(3, Node(1), Node(6)), Node(10, None, Node(14)))

A tree made of trees

Look at the left child of the root in that line: Node(3, Node(1), Node(6)). It's built in just the same way as the whole tree, only smaller. Any node, together with everything below it, is a tree in its own right, a subtree. So a question about a tree can be answered by asking the same question about its two subtrees and adding what the node at the top brings. That's a recursive function, and the empty tree, None, makes a handy base case.

Counting the nodes shows how. An empty tree has 0 nodes. Any other tree has its root, which is 1 node, plus the nodes of its left subtree, plus the nodes of its right subtree:

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


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


tree = Node(8, Node(3, Node(1), Node(6)), Node(10, None, Node(14)))
print(count_nodes(tree))
print(count_nodes(tree.left))

6
3

count_nodes(tree.left) counts only the subtree of 3, 1 and 6. The calls stop at the leaves: a leaf's left and right are both None, and a call that gets None returns 0 straight away.

Without the check for None, the calls run into the missing children of the leaves:

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


def count_nodes(node):
    return 1 + count_nodes(node.left) + count_nodes(node.right)


print(count_nodes(Node(5)))

Traceback (most recent call last):
  File "main.py", line 12, in <module>
    print(count_nodes(Node(5)))
          ~~~~~~~~~~~^^^^^^^^^
  File "main.py", line 9, in count_nodes
    return 1 + count_nodes(node.left) + count_nodes(node.right)
               ~~~~~~~~~~~^^^^^^^^^^^
  File "main.py", line 9, in count_nodes
    return 1 + count_nodes(node.left) + count_nodes(node.right)
                           ^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'left'

The leaf's left is None, and None has no attributes. Whenever you see 'NoneType' object has no attribute, look for a missing check for None.

Printing every value

A function that prints the values has the same shape. It has nothing to return, so for an empty tree it simply returns, and for any other tree it prints the node's value and then hands each subtree to a call of its own:

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


def print_values(node):
    if node is None:
        return
    print(node.value)
    print_values(node.left)
    print_values(node.right)


tree = Node(8, Node(3, Node(1), Node(6)), Node(10, None, Node(14)))
print_values(tree)

8
3
1
6
10
14

Follow the calls. The call for the root prints 8 and then calls the function for the subtree of 3. That call prints 3 and calls the function for 1, which prints 1 and finds None on both sides. Next the call for 3 deals with 6. Only when the subtree of 3 is done does the call for the root get to its last line and move on to 10. Where the print stands decides the order: here it comes before the two calls, so every node is printed before the nodes below it.