Trees: words and shapes

Why trees?

Arrays, stacks and linked lists put items in a line. Many things in life are not a line but a hierarchy: folders inside folders, a company org chart, an HTML page where tags sit inside tags (the DOM), a family tree, or product categories such as Electronics → Mobiles → Smartphones. A tree is the data structure for hierarchies. It also gives fast searching when it is kept in order (binary search trees, Topic 4) and fast "give me the smallest" when it is kept as a heap (Module 8).

The words

A tree has no cycles: from the root there is exactly one path to every node. That single-path rule is what separates a tree from a general graph (Module 9).

Binary trees and their shapes

In a binary tree each node has at most two children, a left child and a right child. Left and right matter: a root with only a left child is a different tree from a root with only a right child.

• Full: every node has 0 or 2 children, never exactly 1.
• Complete: every level is completely filled except possibly the last, and the last level is filled from the left with no gaps. Heaps are complete trees.
• Perfect: every internal node has 2 children and all leaves are on the same level. A perfect tree of height h has 2^(h + 1) − 1 nodes, for example 7 nodes for height 2.
• Balanced (height-balanced): at every node, the heights of the left and right subtrees differ by at most 1. Its height is O(log n).
• Skewed (degenerate): every node has only one child, so the tree is really a linked list and its height is n − 1.

The shape decides the speed. Most tree operations walk from the root down one path, so they cost O(h), where h is the height. In a balanced tree h is about log₂ n (around 20 for a million nodes); in a skewed tree h is n − 1. That difference is the whole reason balanced trees exist.

Representation 1: linked nodes

The usual way is a small class with a value and two links. None means "no child". In this module every task gives you the same TreeNode class and a build(values) helper. build takes a level-order list, the way LeetCode shows trees: the root first, then its children left to right, then the next level, with None for a missing child.

        1
       / \
      2   3
     / \   \
    4   5   6

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

root = build([1, 2, 3, 4, 5, None, 6])
print(root.val, root.left.val, root.right.val)    # Output: 1 2 3
print(root.left.left.val, root.right.right.val)   # Output: 4 6
print(root.right.left)                            # Output: None

Representation 2: an array (heap layout)

A complete binary tree can live in a plain list with no links at all. Put the root at index 0 and fill each level left to right. Then for the node at index i: the left child is at 2i + 1, the right child at 2i + 2, and the parent at (i − 1) // 2. No pointers are stored, which saves memory and keeps the data side by side. Heaps (Module 8) use exactly this layout.

arr = [1, 2, 3, 4, 5, None, 6]
i = 1                     # the node with value 2
print(arr[2 * i + 1], arr[2 * i + 2], arr[(i - 1) // 2])   # Output: 4 5 1

Your first recursive tree function

Almost every tree function follows one template: handle the empty tree (None), then combine the answers of the left and right subtrees. Counting nodes: an empty tree has 0 nodes; otherwise it is 1 (this node) plus the count on the left plus the count on the right. It visits each node once, so it is O(n) time, and the recursion goes as deep as the tree, so it uses O(h) stack space.

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

print(count_nodes(build([1, 2, 3, 4, 5, None, 6])))   # Output: 6

Common mistakes

• Forgetting the empty tree. root.left on None raises AttributeError. Fix: start every function with if root is None.
• Mixing up depth and height, or edges and nodes. Fix: say "height in edges" or "depth in nodes" out loud, and test a single node.
• Treating a leaf as "a node with at most one child". A leaf has NO children: node.left is None and node.right is None.
• Assuming every binary tree is a BST or balanced. Fix: only use ordering or O(log n) when the problem promises it.
• Using the array layout for a sparse tree. A skewed tree of 30 nodes would need about a billion slots. Fix: use linked nodes unless the tree is complete.