DSA Trees

Binary Trees

Why does a − b become b − a if you swap the children of a subtraction node? Because a treats left and right as ordered positions, not an unordered bag of kids.

Shape labels (, , , ) are independent properties. Ordering invariants (BST, heap) are separate contracts layered on the same skeleton.

Decision panel

Two ordered slots

Left and right matter even when one is empty.

Name the shape goal

Full? Complete? Height-balanced? Perfect?

Do not assume order

Binary ≠ sorted. Search needs a BST (or other) invariant.

Cost follows height

A skewed chain makes DFS depth Θ(n).

What actually happens

Naive idea: “binary tree” means fast search. Wrong. Without an ordering invariant, finding a value still scans Θ(n) nodes in the worst case.

Better idea: treat the binary tree as a positional structure. Use it for expression trees, Huffman leaves, heap arrays, or as the host for a BST/heap invariant. Measure height and width explicitly.

The improved design still fails when you prune a subtree as if it were a BST, confuse edge-height with node-height, or call a merely full tree “balanced.” A shape quietly turns every walk into a linked list.

Invariant

Each node exposes at most two child positions, and left versus right is part of the tree's identity. Empty children are meaningful absences, not missing fields to ignore.

How to choose binary tree machinery

1. Need ordered keys? Add a search-tree invariant (or use a balanced BST). Plain binary shape is not enough.

2. Need priority / array locality? Prefer a shape and heap order in an array.

3. Need expression / syntax structure? Ordered left/right slots are the point; balance is optional.

Quantitative check

At height h, a binary tree holds at most 2^h+1 − 1 nodes. So n = 10⁵ forces h ≥ ⌈log₂(n+1)⌉ − 1 ≈ 16 if perfect, but a chain needs h = n − 1 = 99999. Same n, radically different walk costs.

Shape is not ordering

“Binary” limits the number of children; it says nothing about key order. A binary search tree adds an ordering invariant, while a binary heap adds a heap-order and completeness invariant.

Ordered, not necessarily sorted

Swapping a left and right child usually creates a different binary tree. That positional meaning lets expression trees distinguish a − b from b − a.

Interactive binary tree demo

Build a tree and inspect how each node exposes a distinct left slot and right slot.

ℹ️ Ready to build a Binary Tree!

Empty Tree

Shape classifications are independent properties

A tree can satisfy several labels at once. A perfect tree is both full and complete; a full tree need not be complete, and a complete tree need not be full.

Tree shape and representation explorer

Change the shape, then compare the pointer view with its implicit level-order array.

Complete

Every level except possibly the last is full; the last level is filled from left to right.

full: No
complete: Yes
perfect: No
height Balanced: Yes

Implicit array

6 values · 6 allocated positions · 100% occupied · height 2

Ai=0

Bi=1

Ci=2

Di=3

Ei=4

Fi=5

0-based: left = 2i + 1 · right = 2i + 2 · parent = floor((i - 1) / 2)

Full, complete, perfect, and balanced

Comparison of binary tree shape classifications
Property	Exact requirement	What it does not guarantee	Why it matters
Full (proper / strict)	Every node has either 0 or 2 children.	Leaves need not share a depth; the tree need not be short.	For a non-empty full tree, leaves = internal nodes + 1.
Complete	Every level before the last is full; last-level nodes occupy the leftmost positions.	The final internal node may have only a left child, so it need not be full.	Dense level-order array storage; heap height is Θ(log n).
Perfect	Every internal node has two children and all leaves share one depth.	No key ordering is implied.	At height h: nodes = 2^h+1 − 1 and leaves = 2^h.
Height-balanced	Common local definition: at every node, subtree heights differ by at most one.	Nodes need not fill levels or have two children.	This local rule yields logarithmic height; other structures may define balance differently.
Degenerate / skewed	Every internal node has one child; “skewed” often means those children all choose one side.	No logarithmic-height performance.	Height is n − 1, so pointer walks can degrade to Θ(n).

Counting facts under the edge-height convention

Nodes at depth d

at most 2^d

Each prior node can contribute at most two children.

Nodes at height h

h + 1 ≤ n ≤ 2^h+1 − 1

A chain realizes the minimum; a perfect tree realizes the maximum.

Null child links

n + 1

For a non-empty tree, among 2n child-pointer fields, only n − 1 represent tree edges.

Leaf relation

n₀ = n₂ + 1

In any non-empty binary tree, leaves equal two-child nodes plus one.

Linked-node implementation and structural queries

A node stores two references even when one or both positions are empty. The routines below define height in edges and verify the full property, not the unrelated BST ordering property.

Python

python

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def size(node):
    if node is None:
        return 0
    return 1 + size(node.left) + size(node.right)

def height(node):
    if node is None:
        return -1          # leaf height becomes 0
    return 1 + max(height(node.left), height(node.right))

def is_full(node):
    if node is None:
        return True
    if (node.left is None) != (node.right is None):
        return False       # exactly one child
    return is_full(node.left) and is_full(node.right)

root = Node(1, Node(2), Node(3))
print(size(root), height(root), is_full(root))  # 3 1 True

Java

java

final class Node<T> {
    final T value;
    Node<T> left;
    Node<T> right;

    Node(T value) { this.value = value; }
    Node(T value, Node<T> left, Node<T> right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

class BinaryTreeAlgorithms {
    static int size(Node<?> node) {
        if (node == null) return 0;
        return 1 + size(node.left) + size(node.right);
    }

    static int height(Node<?> node) {
        if (node == null) return -1; // leaf height becomes 0
        return 1 + Math.max(height(node.left), height(node.right));
    }

    static boolean isFull(Node<?> node) {
        if (node == null) return true;
        if ((node.left == null) != (node.right == null)) return false;
        return isFull(node.left) && isFull(node.right);
    }

    public static void main(String[] args) {
        Node<Integer> root = new Node<>(1, new Node<>(2), new Node<>(3));
        System.out.println(size(root) + " " + height(root) + " " + isFull(root));
        // 3 1 true
    }
}

Traversal and operation costs

Complexity of operations on an ordinary binary tree
Task	Time	Auxiliary space	Notes
DFS traversal	Θ(n)	O(h)	Recursive stack or an explicit stack follows one root-to-leaf path.
Breadth-first traversal	Θ(n)	O(w)	`w` is maximum width; a perfect tree can queue Θ(n) nodes.
Find arbitrary value	O(n)	O(h) or O(w)	Without a search-order invariant, either subtree may contain it.
Compute size / height	Θ(n)	O(h)	Cached metadata makes reads O(1) but complicates mutations.

Representation choice

Linked nodes: preserve arbitrary shape and support local rewiring, at the cost of references and scattered allocation.
Level-order arrays: remove pointers and improve locality for complete trees.
Succinct encodings: compress mostly static tree shapes and add rank/select metadata for navigation.

Counterexample to “binary ⇒ fast”

Insert keys 1..n in ascending order into a structure that only enforces binary shape (or a plain BST). The result is a right spine. Search for n examines every node. The binary branching factor never helped because the shape never branched.

Applications follow the invariant

Expression and syntax trees use ordered child positions; binary heaps use completeness and heap order; search trees add key ordering; Huffman coding assigns symbols to leaves; tournament and decision trees model pairwise outcomes or binary choices. “Binary tree” describes the skeleton: the added invariant supplies the algorithmic power.

Exercises

Draw one tree that is full but not complete, and one that is complete but not full. For each, state height and leaf count under the edge convention.
Prove n₀ = n₂ + 1 for any non-empty binary tree. Where does the identity fail if unary nodes are allowed without the full restriction?
For n = 2²⁰ − 1, what height does a perfect tree need? What height does a skewed tree need? How does that change BFS queue vs DFS stack peak size?

Primary sources

Cormen et al., Introduction to Algorithms (CLRS): binary trees, heaps as nearly complete binary trees.
Knuth, TAOCP Vol. 1: binary tree enumerations and left-child/right-sibling encoding.
Weiss, Data Structures and Algorithm Analysis: full/complete/perfect distinctions and height bounds.

Takeaway

A binary tree is two ordered child slots plus a shape. Speed and sortedness come only from extra invariants (balance, search order, heap order), never from the word “binary” alone.