Skip to main content

Data Structures: Binary Trees

· 6 min read
tanzhuo

Linked lists and arrays solve the problem of storing "linear" data, but once hierarchy or fast lookup comes into play, linear structures fall short. Tree structures exist precisely for this, and the binary tree is the most fundamental and most frequently tested one among them—heaps, BSTs, and red-black trees are all built on top of it.

A binary tree is a common data structure made up of nodes, where each node has at most two children:

  • Left child
  • Right child

Hence the name binary tree.

The "at most two" constraint looks simple, but it brings an important property: the tree's shape can be defined recursively—every binary tree consists of a root node, a left subtree, and a right subtree, and the left and right subtrees are themselves binary trees. Nearly every binary tree algorithm that follows (traversal, search, insertion) is built around this recursive structure.

Each node typically has three parts:

Node {
    value   // the data stored in the node
    left    // reference to the left child, or null if none
    right   // reference to the right child, or null if none
}

In other words, a binary tree doesn't require contiguous storage in memory; nodes are connected by references (pointers), much like a linked list—except each node goes from "one successor" to "at most two children."

A simple example:

        A
       / \
      B   C
     / \   \
    D   E   F

Here:

  • A is the root
  • B and C are A's children
  • D and E are B's children

Nodes with no children (like D, E, F) are called leaf nodes. The number of levels from the root down to a leaf is the tree's height, which directly determines the cost of most operations on the tree.

Based on shape, binary trees come in a few common special forms—let's go through them one by one.

Full Binary Tree​

If every node in the tree has either two children or no children, it's a full binary tree.

        A
       / \
      B   C
     / \ / \
    D  E F  G

Characteristics:

  • Every node has either 0 children
  • or 2 children

In other words, a full binary tree has no node with "only one child." This is the most densely packed shape—for a given number of levels, it holds the most nodes.

Complete Binary Tree​

A complete binary tree requires:

  • Every level except the last is completely filled
  • Nodes in the last level are packed contiguously from left to right

Example:

        1
       / \
      2   3
     / \  /
    4  5 6

This structure is perfect for array storage, which is why the heap is a complete binary tree.

Why is a complete binary tree so well suited to arrays? Because numbering nodes "top to bottom, left to right" leaves no gaps in the middle: put the root at index 0, and the node at index i has its left child at 2i + 1, right child at 2i + 2, and parent at (i - 1) / 2 (rounded down). No pointers need to be stored—index arithmetic alone lets you jump between parent and child, which saves memory and is cache-friendly. Heapsort and priority queues exploit exactly this.

Binary Search Tree (BST)​

The two categories above are about "shape"; the binary search tree is about "how node values are arranged." A binary search tree satisfies:

left subtree < root < right subtree

Note that this constraint applies recursively: it's not just the immediate children—every value in the entire left subtree is less than the root, and every value in the entire right subtree is greater.

Example:

        8
       / \
      3   10
     / \    \
    1   6    14

Characteristics:

  • Fast lookups
  • Average time complexity: O(log n)

Searching works just like binary search: start at the root, go left if the target is smaller than the current node, go right if it's larger, and each level down eliminates roughly half the candidates. Insertion works the same way—follow the search path to an empty slot and hang the new node there.

But if the tree degenerates into a linked list:

1
 \
  2
   \
    3

the time complexity degrades to:

O(n)

The classic trigger for degeneration is inserting values in sorted order: each new node is larger than all previous ones, so it can only keep hanging off the right side. The tree "grows crooked" into a chain, each level of a search eliminates only one node, and the BST's advantage vanishes entirely. This is exactly why self-balancing binary search trees like AVL trees and red-black trees exist—they restructure via rotations on insert and delete, keeping the tree height at O(log n).

Traversals​

Visiting all the nodes of a binary tree is called traversal. There are four common kinds:

  1. Preorder: root → left subtree → right subtree; often used for copying or serializing a tree
  2. Inorder: left subtree → root → right subtree; for a BST, an inorder traversal yields the values in ascending order
  3. Postorder: left subtree → right subtree → root; suited to "handle the children before yourself" scenarios, like freeing an entire tree
  4. Level-order: visit level by level, left to right, implemented with a queue—breadth-first search on a tree

The first three are very natural to write recursively, which confirms the point from earlier: a binary tree is itself a recursively defined structure.

Pitfalls and Caveats​

A few things that trip people up in practice and in coding interviews:

  • Don't assume a BST is balanced. When analyzing complexity, distinguish "average O(log n)" from "worst-case O(n)"—the follow-up question in interviews is usually about the degenerate case.
  • Validate a BST with an inorder traversal. To check whether a tree is a valid BST, comparing each node with just its immediate children isn't enough—the entire subtree must satisfy the ordering. Checking that the inorder sequence is strictly increasing is the least error-prone approach.
  • Recursion depth. When the tree degenerates into a chain, the call stack of a recursive traversal is also O(n), which can overflow the stack on large inputs; switch to an iterative version with an explicit stack when necessary.
  • Distinguish "full" from "complete". The two definitions are easy to mix up: a full binary tree forbids single-child nodes, while a complete binary tree requires the last level to be left-aligned. True/false questions love pitting these two concepts against each other.

Summary​

The binary tree is one of the most fundamental and important data structures. Its core traits:

  • Each node has at most two children
  • Supports efficient search
  • Extends into many advanced data structures

Common variants include:

  • Binary search tree (BST)
  • AVL tree
  • Red-black tree
  • Heap

Understanding binary trees is an essential foundation for learning algorithms and data structures. Once you've internalized the recursive definition, the differences between the common shapes, and the traversal patterns, you'll find that balanced trees and heaps—those "advanced" structures—are really just binary trees with extra constraints layered on.

COMMENTS