Binary Tree Types and Properties - PCCST303

Definition

A binary tree is a tree in which every node has at most two children, conventionally called the left child and the right child.

Not all binary trees look alike. Depending on how strictly the children are arranged, a binary tree can take on a handful of recognizable shapes, each with its own name, its own rules, and its own uses.

KTU PYQ

KTU PYQ, November 2025, Q14(b), 3 marks: "Explain the following terms with examples: i) Full binary tree ii) Complete binary tree."

To answer this, give the definition and one example diagram for each term. The purple-bordered sections below answer this.

Full binary tree

Definition

A binary tree is full (also called a proper or strict binary tree) if every node has exactly zero children or exactly two children, never exactly one.

This tree is full: A and B each have two children, and C, D, E have none.

Key Idea

This must hold for every node in the tree, not just the root or a few of them. If even one node anywhere in the tree has only a left child or only a right child, the whole tree is not full.

This tree is not full, since A has exactly one child.

Full binary tree property

For a full binary tree, the number of leaves and the number of internal nodes are related by a fixed formula:

L = I + 1

where L is the number of leaves and I is the number of internal nodes (nodes with at least one child). For the full tree above: internal nodes {A, B} give I = 2, and leaves {C, D, E} give L = 3, matching 3 = 2 + 1.

Complete binary tree

Definition

A binary tree is complete if every level except possibly the last is completely filled, and the last level is filled from left to right.

This tree is complete: the last level (D, E) is filled starting from the left, with no gaps.

This tree is not complete: B's left child is missing while B's right child (E) is present, a gap before the last level is filled left to right.

Full vs complete

Property	Full	Complete
Every node has 0 or 2 children	Required	Not required
A node can have exactly 1 child	No	Possible
Last level filled left to right	Not required	Required

Full and complete are independent properties, neither implies the other. A tree can be full but not complete, complete but not full, both, or neither.

Perfect binary tree

Definition

A binary tree is perfect if every internal node has exactly two children, and all leaves sit at the same level.

Every perfect tree is both full and complete, but a full-and-complete tree isn't automatically perfect unless every level is entirely filled.

For height h (measured in edges, root at height h, leaves at height 0):

number of nodes = 2^h+1 − 1
number of leaves = 2^h

For h = 2 (the tree above): nodes = 2³ − 1 = 7, matching the 7 nodes drawn.

Skewed binary tree

Definition

A skewed binary tree is a binary tree in which every node has at most one child.

Key Idea

With no node ever branching two ways, a skewed tree degenerates into a shape that behaves exactly like a linked list.

Left-skewed: every node's only child is a left child.

Right-skewed: every node's only child is a right child.

A skewed tree is the worst-case shape for a binary tree. Since the tree has little or no branching, finding a node may require following a long path from the root to the leaf, taking O(n) time instead of the O(log n) time possible in a well-balanced tree.

Balanced binary tree

Definition

A binary tree is balanced if, at every node, the heights of its left and right subtrees never differ by more than a small, fixed amount (commonly at most 1).

A balanced binary tree doesn't let one side grow much taller than the other. At every node, the height of the left subtree and the height of the right subtree are kept close, never too far apart. This keeps the overall height near the smallest it could possibly be for that many nodes, around O(log n).

A skewed tree is the opposite extreme. It has no such constraint, so its height can grow all the way to O(n).

Maximum nodes by level and height

For a binary tree with the root at level 0:

maximum nodes at level i = 2ⁱ

Summing across all levels up to height h gives the maximum node count for a binary tree of that height:

1 + 2 + 4 + ... + 2^h = 2^h+1 − 1

For height = 3: maximum nodes = 2⁴ − 1 = 15. This is the same formula as the perfect-tree node count, since a perfect tree is exactly the shape that reaches the maximum node count for its height.

Quick recall

Full: every node has 0 or 2 children. Property: leaves = internal nodes + 1.
Complete: every level full except possibly the last, and the last level fills left to right.
Perfect: full and every leaf at the same level; node count 2^h+1 − 1.
Skewed: every node has at most one child, degenerates toward a linked list, height O(n).
Balanced: height kept near O(log n) by limiting subtree height difference.
Full and complete are independent properties; check each separately.