Skip to content
Tutorials Center
My learning

Topics

Lesson 90 of 225 ยท Trees

Binary Trees

Learn binary trees from scratch in Python: the node class, full, complete, perfect and balanced trees, array storage, building trees and counting nodes and height.

A binary tree is a tree in which every node has at most two children, called the left child and the right child. That tiny restriction is what makes binary trees so useful: with only two directions to choose from, algorithms become simple recursions, and when the tree is shaped well, you can find things by discarding half of the data at every step.

In the previous lesson you met general trees with any number of children. This lesson builds the binary version from scratch: the node class, the vocabulary for describing a tree's shape (full, complete, perfect, balanced), the surprising way a tree can live inside a plain list, and the first recursive functions you will write over and over: count the nodes, measure the height, and sum the values.

The node

A binary tree is nothing more than nodes that point to other nodes, exactly like a linked list, except each node has two outgoing pointers instead of one.

graph TD
    A((8)) --> B((3))
    A --> C((10))
    B --> D((1))
    B --> E((6))
    C --> R[" "]:::empty
    C --> F((14))
    classDef empty fill:none,stroke:none

A binary tree: every node has at most two children, called left and right. Node 8 is the root; nodes 1, 6 and 14 are leaves.

TEXT
        1            <- root
       / \
      2   3
     / \   \
    4   5   6        <- 4, 5 and 6 are leaves

Each node stores a value and two references. A missing child is None. The whole tree is represented by a reference to its root; an empty tree is simply None.

Python A binary tree node, built by hand

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice how the code mirrors the picture: TreeNode(2, TreeNode(4), TreeNode(5)) reads "a node 2 whose children are 4 and 5". Writing trees as nested constructor calls is fine for small examples; later we will build them from a list.

Vocabulary you need

You already know root, leaf, parent and child. Binary trees add terms about shape. Interview questions and library documentation use these words precisely, so it pays to learn them exactly.

Name Rule Example
Full (strict) Every node has 0 or 2 children, never exactly 1 A node with one child breaks it
Perfect Full, and all leaves are on the same level 1, 3, 7, 15, ... nodes
Complete Every level is full except possibly the last, which is filled from the left A binary heap's shape
Balanced For every node, the heights of its two subtrees differ by at most 1 AVL trees guarantee this
Degenerate (skewed) Every node has one child; the tree is a linked list in disguise Inserting sorted data into a plain BST
TEXT
Perfect (7 nodes)     Complete (6 nodes)    Degenerate (4 nodes)
      1                     1                   1
    /   \                 /   \                  \
   2     3               2     3                  2
  / \   / \             / \   /                    \
 4   5 6   7           4   5 6                      3
                                                     \
                                                      4

These properties are independent, so test each definition on its own. The middle tree above is complete but not full, because node 3 has only one child. A tree can also be full without being complete, or both at once (every perfect tree is both).

Height and the number of nodes

The height of a tree is the number of edges on the longest path from the root down to a leaf. (Some books count nodes instead; we count edges, so a single node has height 0 and, by convention, the empty tree has height -1.) The height decides how fast everything else is, so it is worth knowing how it relates to the node count n:

  • A perfect tree of height h has exactly 2^(h+1) - 1 nodes. Height 3 gives 15 nodes.
  • So a tree with n nodes can have a height as small as about log2(n): one million nodes fit in a tree of height 19.
  • A degenerate tree with n nodes has height n - 1.

That gap between log n and n is the entire reason people care about keeping trees balanced. We return to it in binary search trees and self-balancing trees.

Recursion: the natural way to walk a tree

A binary tree is a recursive structure: the left child is the root of a smaller binary tree, and so is the right child. A function that handles a tree can handle the empty tree directly (the base case) and trust itself to handle both subtrees (the recursive case).

TEXT
count(node):
    if node is empty:  return 0
    return 1 + count(left) + count(right)
Python Count nodes, leaves, height and sum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All four functions follow the same skeleton: base case for None, combine the answers from both children. Each visits every node exactly once, so each runs in O(n) time. The extra space is the recursion stack, which is O(h) where h is the height: tiny for a balanced tree, O(n) for a skewed one.

Python limits recursion depth to about 1000 frames. A degenerate tree with 5,000 nodes would crash these recursive functions with RecursionError. For such inputs, use an iterative version with an explicit stack or queue (traversals shows how).

Building a tree from a list

Typing nested constructors does not scale. Competitive-programming sites and tests usually describe a tree as a level-order list where None marks a missing child, for example [1, 2, 3, 4, 5, None, 6]. We read the list left to right and attach children to nodes taken from a queue.

Python Build a tree from a level-order list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Turn your head 90 degrees to the left to read the printout: the root is at the left edge, and children are indented deeper. Keep build_tree and show in your toolbox; the tree lessons that follow use them.

Checking the shape

How would you test whether a tree is full, perfect, or complete? Full and balanced fall out of recursion. Complete needs one observation: in a level-order walk of a complete tree (visiting empty slots too), once you have seen a missing child you must never see another real node.

Python Full, perfect, complete and balanced checks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Study the table it prints. The "full" sample is full but neither perfect nor complete, and the "complete" sample is not full because node 3 has only a left child. The is_balanced helper uses a trick worth remembering: one pass returns the height and, at the same time, a sentinel (-2) meaning "already failed". Calling height at every node instead would cost O(n^2) on a skewed tree.

Storing a tree in an array

A complete tree needs no pointers at all. Number the nodes level by level starting from 0, and the family relationships become arithmetic:

TEXT
index:    0
        /   \
       1     2
      / \   /
     3   4 5

array: [A, B, C, D, E, F]
parent of i:       (i - 1) // 2
left child of i:   2*i + 1
right child of i:  2*i + 2

This is how binary heaps are stored (see binary heaps). It is compact and cache-friendly because there are no node objects or pointers. The catch: for a tree that is not complete, you must leave empty slots, and a skewed tree of height h would need an array of about 2^h cells, almost all wasted. That is why general binary trees use linked nodes.

Python Array representation: parent and children

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last line shows the waste: a right-leaning chain of depth 4 puts its deepest node at index 30, so 31 cells would be needed for 5 nodes.

Complexity

Operation Linked tree Notes
Count / sum / height O(n) time, O(h) space visits every node once
Access the root O(1)
Find a value (unordered tree) O(n) no order to exploit
Space for the tree O(n) one node object per element

A plain binary tree gives no ordering guarantee, so searching it is a full scan. The binary search tree adds an ordering rule that turns searching into O(h).

Common mistakes

  • Forgetting the None base case. Accessing node.left when node is None raises AttributeError. Every recursive tree function starts with the empty check.
  • Mixing up height conventions. Decide whether a single node has height 0 (edges) or 1 (nodes), and be consistent. Interview questions usually say which.
  • Confusing "complete" with "full". Complete is about filling levels from the left; full is about every node having 0 or 2 children.
  • Using the array formulas on an incomplete tree without leaving gaps for missing children.
  • Mutating while traversing. Changing left/right pointers in the middle of a walk can detach subtrees you still need.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the maximum number of nodes in a binary tree of height 3 (counting height in edges)?

    A perfect tree of height h has 2^(h+1) - 1 nodes, so height 3 gives 2^4 - 1 = 15.
  2. 2. Which tree is described by: every node has either 0 or 2 children?

    That is the definition of a full (strict) binary tree. Perfect is stricter: it must also have all leaves on one level.
  3. 3. In the array representation of a complete binary tree, where is the left child of the node at index 4?

    left(i) = 2i + 1 = 9. Index 8 would be 2i, which is the formula for 1-based arrays.
  4. 4. What must the recursive height function return for an empty tree if a single node should have height 0?

    A leaf computes 1 + max(h_left, h_right), which only equals 0 when the empty tree returns -1.
  5. 5. A tree with n nodes is degenerate (every node has one child). What are its height and the stack space of a recursive height function?

    A chain of n nodes has n - 1 edges, and the recursion goes as deep as the tree is tall, so the call stack holds O(n) frames.

Summary

  • A binary tree node holds a value and up to two children; the tree is a reference to its root, and the empty tree is None.
  • Shape words: full (0 or 2 children), perfect (full with all leaves on one level), complete (levels filled left to right), balanced (subtree heights differ by at most 1), degenerate (a chain).
  • Perfect trees of height h have 2^(h+1) - 1 nodes; a tree with n nodes has height between about log2 n and n - 1.
  • Most tree functions are recursions with a None base case; they run in O(n) time and O(h) stack space.
  • Complete trees fit in an array with parent = (i-1)//2, left = 2i+1, right = 2i+2; this is how heaps are stored.
  • Build test trees from level-order lists with None for gaps.

Next: Tree Traversals