Binary tree introduction

Binary trees

A binary tree is a bunch of nodes where each one has a value and up to two children — a left child and a right child. It branches instead of forming a straight chain like a linked list, more like a family tree than a queue.

The node

TreeNode:
    value
    left    // reference to the left child, or nothing
    right   // reference to the right child, or nothing

Either child can be nil. You hold a tree by holding its root (the topmost node). A node with no children is a leaf.

      3          <- root
     / \
    9   20
       /  \
      15   7     <- 9, 15, 7 are leaves

Why trees?

Trees model anything hierarchical — file systems, the DOM, decision processes — and a balanced binary search tree gives O(log n) search, insert, and delete. The shape of the branching is the whole point.

How we'll write trees

Throughout this section a tree is given in level order (top to bottom, left to right), using x for a missing child. The tree above is:

3 9 20 x x 15 7

Read it level by level: 3; then 3's children 9 and 20; then 9's children (x x, none) and 20's children 15 and 7. An empty line (or a leading x) is the empty tree.

The key idea: recursion

Every subtree is itself a tree. That's why almost every tree algorithm is recursive: do something with the current node, then recurse on Left and Right. The next lessons cover the vocabulary and the two ways to walk a tree.