Binary Trees

Think of the guessing game where you pick an animal and a friend asks yes-or-no questions. "Does it live in water?" Yes. "Does it have legs?" No. "Is it bigger than a person?" Yes. "Is it a whale?"

Write all the possible questions on cards and lay them out. Each card leads to two more cards, one for yes and one for no, until a card holds a final guess instead of a question. That layout is a binary tree. Most problems on binary trees are solved with the same short pattern.

#The parts of a tree

A binary tree is made of nodes. Each node holds a value and has up to two children, called left and right. The words you need:

• The root is the single node at the top. Nothing points to it.
• A leaf is a node with no children.
• A node's parent is the node directly above it. Every node except the root has exactly one.
• A subtree is any node together with everything below it.
• The depth of a node is how many steps it is from the root. The root has depth 0.
• The height of a tree is the number of nodes on its longest path from the root down to a leaf. An empty tree has height 0.

In code, a node is a tiny object with three fields: val, left and right. A missing child is null in JavaScript or None in Python. It is like a linked list node that points two ways instead of one.

#The one pattern: ask both children

Here is the sentence that makes trees easy: a binary tree is either empty, or a node with a left tree and a right tree hanging from it. The children are smaller trees of exactly the same kind.

That means you can answer most questions about a tree with recursion in three moves:

1. Empty tree: return the obvious answer (0 nodes, height 0, sum 0).
2. Ask both children the same question.
3. Combine their two answers with the current node.

Take height. If you knew the height of the left subtree and the height of the right subtree, the height of the whole tree is the taller of the two, plus 1 for the current node. You do not have to think about the whole tree at once. Each node only does one small calculation.

#Tracing height by hand

Here is the tree from the figure. A node cannot finish until both of its children have reported back, so the answers fill in from the bottom up. Green nodes are finished.

height(node):  if node is empty: return 0  left = height(node.left)  right = height(node.right)  return 1 + max(left, right)

#The code

Height and node count have the same skeleton. Only the combine line differs.

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}
 
// Number of nodes on the longest path down from node.
function height(node) {
  if (node === null) return 0; // empty tree
  return 1 + Math.max(height(node.left), height(node.right));
}
 
function countNodes(node) {
  if (node === null) return 0;
  return 1 + countNodes(node.left) + countNodes(node.right);
}
 
// The tree from the trace: 6 on top, 2 and 9 below it.
const root = new TreeNode(6,
  new TreeNode(2, new TreeNode(4, null, new TreeNode(1))),
  new TreeNode(9, null, new TreeNode(7)));
height(root);     // 4
countNodes(root); // 6

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
# Number of nodes on the longest path down from node.
def height(node):
    if node is None:  # empty tree
        return 0
    return 1 + max(height(node.left), height(node.right))
 
def count_nodes(node):
    if node is None:
        return 0
    return 1 + count_nodes(node.left) + count_nodes(node.right)
 
# The tree from the trace: 6 on top, 2 and 9 below it.
root = TreeNode(6,
    TreeNode(2, TreeNode(4, None, TreeNode(1))),
    TreeNode(9, None, TreeNode(7)))
height(root)       # 4
count_nodes(root)  # 6

function countLeaves(node) {
  if (node === null) return 0;
  if (node.left === null && node.right === null) return 1; // a leaf
  return countLeaves(node.left) + countLeaves(node.right);
}

def count_leaves(node):
    if node is None:
        return 0
    if node.left is None and node.right is None:  # a leaf
        return 1
    return count_leaves(node.left) + count_leaves(node.right)

#Cost: time and the shape of the tree

Each function calls itself once per node and does a constant amount of work there, so the time is O(n). The calls on empty children do not change that: a tree with n nodes has exactly n + 1 empty child slots, so they add at most n + 1 more cheap calls.

Space is less obvious. While a call waits for its children, it sits on the call stack. The deepest the stack gets is the height of the tree, h. And height depends on the shape.

In a bushy tree, each level holds twice as many nodes as the one above, so a million nodes fit in about 20 levels: height is about log₂ n. In a stick, every node has one child and the height is n. Recursive tree functions use O(h) stack space, and the search trees in later lessons take O(h) time per operation, so the shape matters a lot.

#Common mistakes

#Check yourself

#What to practise next

Height visited every node in one particular order: children before parent. Tree Traversals covers all the useful orders, including level by level, and how to walk a tree without recursion.