Trees & Binary Trees

Lists, stacks and queues are linear: every item has at most one item after it. Much real data is not like that. A company has a CEO with several managers, each with their own team. A folder holds files and other folders. A family tree branches at every generation. A tree is the data structure for this kind of branching, hierarchical data.

In this lesson you will learn the vocabulary of trees, build a general tree and a binary tree in Python, write the recursive functions every tree problem builds on, and see how a complete binary tree can be stored in a plain list.

Tree vocabulary

A tree is made of nodes connected by edges. Each edge links a parent to a child. The words below appear in every tree problem, so learn them now:

A tree with n nodes always has exactly n - 1 edges, because every node except the root has exactly one parent. There are no loops: from the root, there is exactly one path to each node. (When loops are allowed, the structure is called a graph, covered in Graphs & Representations.)

A general tree

In a general tree, a node can have any number of children, so each node keeps a list of them. Here is the staff structure of a school in Rohtak:

class TreeNode:
    def __init__(self, name):
        self.name = name
        self.children = []

    def add(self, child):
        self.children.append(child)
        return child

principal = TreeNode("Principal")
science = principal.add(TreeNode("Science HoD"))
arts = principal.add(TreeNode("Arts HoD"))
principal.add(TreeNode("Accounts"))
science.add(TreeNode("Physics: Mr Verma"))
science.add(TreeNode("Chemistry: Ms Iyer"))
arts.add(TreeNode("History: Mrs Khan"))

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

def count(node):
    return 1 + sum(count(child) for child in node.children)

show(principal)
print("Total staff:", count(principal))

Principal
    Science HoD
        Physics: Mr Verma
        Chemistry: Ms Iyer
    Arts HoD
        History: Mrs Khan
    Accounts
Total staff: 7

Notice that both functions are recursive, and that is no accident: a tree is a root plus a list of smaller trees. Almost every tree function works by asking each child's subtree for an answer and combining the answers. The base case is a leaf, whose list of children is empty, so the loop simply does nothing.

Binary trees

A binary tree is a tree where every node has at most two children, called left and right. Binary trees are the basis of binary search trees, heaps, expression trees and many interview problems.

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

#            8
#          /   \
#         3     10
#        / \      \
#       1   6      14
#          / \
#         4   7
root = Node(8,
            Node(3, Node(1), Node(6, Node(4), Node(7))),
            Node(10, None, Node(14)))

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

def height(node):
    if node is None:
        return -1                  # an empty tree has height -1
    return 1 + max(height(node.left), height(node.right))

def leaves(node):
    if node is None:
        return []
    if node.left is None and node.right is None:
        return [node.value]
    return leaves(node.left) + leaves(node.right)

print("size:", size(root))
print("height:", height(root))
print("leaves:", leaves(root))

size: 8
height: 3
leaves: [1, 4, 7, 14]

The pattern is always the same: handle None (the empty tree) as the base case, then combine the answers for node.left and node.right. Each function visits every node once, so each is O(n). The recursion goes as deep as the tree is tall, so the extra space is O(h) for a tree of height h.

The choice that an empty tree has height -1 makes a single node come out as height 0, matching the definition "edges on the longest path". Some books count nodes instead of edges, so a single node has height 1. Either is fine if you are consistent; say which one you use in an interview.

Shapes of binary trees

The shape of a binary tree decides how fast operations on it are, because most operations walk from the root down one path.

A perfect tree with 20 levels holds over ten lakh nodes, so a path from the root to any leaf is just 19 edges. A degenerate tree with the same nodes is ten lakh nodes deep. Keeping trees balanced is the whole point of the balanced search trees you will meet in Binary Search Trees.

Storing a complete tree in a list

A complete binary tree has no gaps, so it can be stored in a plain list in level order (top to bottom, left to right) with no node objects at all. For the node at index i:

• its left child is at index 2 * i + 1,
• its right child is at index 2 * i + 2,
• its parent is at index (i - 1) // 2.

This is exactly how heaps are stored, as you will see in Heaps & Priority Queues. Interview problems also often give a tree as a level-order list with None for missing nodes. This function builds node objects from that format using a queue:

from collections import deque

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

def build(level_order):
    if not level_order or level_order[0] is None:
        return None
    values = iter(level_order)
    root = Node(next(values))
    waiting = deque([root])            # nodes whose children are not set yet
    for left_value in values:
        parent = waiting.popleft()
        if left_value is not None:
            parent.left = Node(left_value)
            waiting.append(parent.left)
        right_value = next(values, None)
        if right_value is not None:
            parent.right = Node(right_value)
            waiting.append(parent.right)
    return root

def show(node, depth=0, label="root"):
    if node:
        print("    " * depth + f"{label}: {node.value}")
        show(node.left, depth + 1, "L")
        show(node.right, depth + 1, "R")

tree = build([50, 30, 70, None, 40, 60, 80])
show(tree)

heap_list = [5, 9, 7, 12, 15]
i = 1
print("children of", heap_list[i], "are", heap_list[2 * i + 1], "and", heap_list[2 * i + 2])
print("parent of", heap_list[4], "is", heap_list[(4 - 1) // 2])

root: 50
    L: 30
        R: 40
    R: 70
        L: 60
        R: 80
children of 9 are 12 and 15
parent of 15 is 9

The None in the input means 30 has no left child, so 40 becomes its right child. The final lines show the index arithmetic on a list stored in level order: the node at index 1 has its children at indexes 3 and 4.

Common mistakes

• Forgetting the None base case. Calling node.left on None raises AttributeError. Check for the empty tree first.
• Mixing up depth and height. Depth is measured down from the root; height is measured up from the deepest leaf.
• Counting nodes instead of edges (or the other way round) without saying so.
• Assuming a tree is balanced. Unless something keeps it balanced, a tree can become a long chain with O(n) height.

Key points

• A tree is hierarchical: one root, every other node has exactly one parent, and there are no loops.
• A tree with n nodes has n - 1 edges.
• Tree functions are recursive: answer for the empty tree, then combine the answers from the subtrees.
• Size, height and leaf-collecting functions visit each node once: O(n) time and O(h) stack space.
• Balanced trees have O(log n) height; degenerate trees have O(n) height.
• A complete binary tree fits in a list: children of index i are at 2i + 1 and 2i + 2.

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

root = Node(8,
            Node(3, Node(1), Node(6, Node(4), Node(7))),
            Node(10, None, Node(14)))

def tree_sum(node):
    if node is None:
        return 0
    return node.value + tree_sum(node.left) + tree_sum(node.right)

def max_value(node):
    if node is None:
        return None
    candidates = [node.value, max_value(node.left), max_value(node.right)]
    return max(v for v in candidates if v is not None)

print(tree_sum(root), max_value(root))
print(tree_sum(root.left), max_value(root.left))

53 14
21 7