Binary Tree Basics & Types
What Is a Binary Tree?
A binary tree is a tree data structure where every node has at most two children — referred to as the left child and the right child. No node may have more than two children. No restrictions are placed on values — a binary tree is a structural definition only.
VALID binary trees:
Single node: One child: Two children: No children:
1 1 1 1
/ / \
2 2 3
ALL valid — each node has at most 2 children.
INVALID (not a binary tree):
1 ← node 1 has 3 children: 2, 3, 4 ✗
/|\
2 3 4
Binary Tree Node Structure
Every node in a binary tree stores three things: the data value, a reference to the left child, and a reference to the right child. Either child reference can be null (no child on that side).
1public class TreeNode {
2
3 int val; // The data stored in this node
4 TreeNode left; // Reference to left child (null if no left child)
5 TreeNode right; // Reference to right child (null if no right child)
6
7 // Constructor — create a node with a value, no children
8 TreeNode(int val) {
9 this.val = val;
10 this.left = null;
11 this.right = null;
12 }
13
14 // Manually building a binary tree:
15 // 1
16 // / \
17 // 2 3
18 // / \
19 // 4 5
20 public static TreeNode buildExample() {
21 TreeNode root = new TreeNode(1);
22 root.left = new TreeNode(2);
23 root.right = new TreeNode(3);
24 root.left.left = new TreeNode(4);
25 root.left.right = new TreeNode(5);
26 return root;
27 }
28
29 public static void main(String[] args) {
30 TreeNode root = buildExample();
31 System.out.println("Root: " + root.val); // 1
32 System.out.println("Left child: " + root.left.val); // 2
33 System.out.println("Right child: " + root.right.val); // 3
34 System.out.println("Left.Left: " + root.left.left.val); // 4
35 System.out.println("Left.Right: " + root.left.right.val); // 5
36 System.out.println("Right.Left: " + root.right.left); // null
37 }
38}Output:
Root: 1
Left child: 2
Right child: 3
Left.Left: 4
Left.Right: 5
Right.Left: null
Memory Representation
A binary tree can be stored in memory using two representations. Understanding both is essential.
Linked Representation (Most Common)
Each node is a separate object in heap memory, connected by left/right pointers:
Memory layout for:
1
/ \
2 3
/ \
4 5
Heap memory (addresses are illustrative):
addr 0x100: [ val=1 | left=0x200 | right=0x300 ] ← root
addr 0x200: [ val=2 | left=0x400 | right=0x500 ] ← node 2
addr 0x300: [ val=3 | left=null | right=null ] ← node 3
addr 0x400: [ val=4 | left=null | right=null ] ← node 4
addr 0x500: [ val=5 | left=null | right=null ] ← node 5
root pointer → 0x100
Following root.left → 0x200 (value 2)
Following root.left.left → 0x400 (value 4)
Following root.right.left → null (node 3 has no left child)
Array Representation (For Complete Trees)
For a complete binary tree, nodes can be stored in a contiguous array using index arithmetic:
Tree: 1
/ \
2 3
/ \ / \
4 5 6 7
Array: [_, 1, 2, 3, 4, 5, 6, 7] (1-indexed, index 0 unused)
0 1 2 3 4 5 6 7
1-indexed formulas:
Left child of i: 2 × i
Right child of i: 2 × i + 1
Parent of i: i / 2
0-indexed formulas (more common in code):
Array: [1, 2, 3, 4, 5, 6, 7]
0 1 2 3 4 5 6
Left child of i: 2 × i + 1
Right child of i: 2 × i + 2
Parent of i: (i - 1) / 2
Verification (0-indexed):
Node at index 1 (value 2):
Left child: 2×1+1=3 → arr[3]=4 ✓
Right child: 2×1+2=4 → arr[4]=5 ✓
Parent: (1-1)/2=0 → arr[0]=1 ✓
ONLY works gap-free for COMPLETE binary trees.
A sparse tree would waste large amounts of array space.
Key Binary Tree Properties
For a binary tree of HEIGHT h:
MAX NODES: a perfect binary tree with h+1 levels has 2^(h+1) - 1 nodes
h=0: 1 node (just root)
h=1: 3 nodes (root + 2 children)
h=2: 7 nodes (3 + 4 grandchildren)
h=3: 15 nodes
MIN NODES (for height h): h + 1 nodes
Achieved by the degenerate (skewed) tree — single chain
MAX NODES AT LEVEL k: 2^k
Level 0 (root): max 1 node
Level 1: max 2 nodes
Level 2: max 4 nodes
Level k: max 2^k nodes
FOR FULL BINARY TREE (every node has 0 or 2 children):
If L = number of leaves and I = number of internal nodes:
L = I + 1 (always true for any full binary tree)
Example: 1 Internal nodes: {1, 2} I = 2
/ \ Leaf nodes: {3,4,5} L = 3
2 3 L = I + 1 = 3 ✓
/ \
4 5
Type 1: Full Binary Tree
A full binary tree (also called a proper or strictly binary tree) is one where every node has either 0 or 2 children — never exactly 1.
FULL binary tree:
1
/ \
2 3
/ \ \ ← node 3 has 1 child — NOT full
4 5 6
NOT full (node 3 has only one child).
FULL binary tree (corrected):
1
/ \
2 3
/ \
4 5
Node 1: 2 children ✓
Node 2: 2 children ✓
Node 3: 0 children ✓ (leaf)
Node 4: 0 children ✓ (leaf)
Node 5: 0 children ✓ (leaf)
Every node has 0 OR 2 children ✓
Another valid full binary tree:
1
/ \
2 3
/ \ / \
4 5 6 7
PROPERTY: In a full binary tree with n nodes: - Number of internal nodes = (n - 1) / 2 - Number of leaf nodes = (n + 1) / 2 - L = I + 1 (leaves = internal + 1) With 7 nodes: I = 3, L = 4, L = I+1 = 4 ✓
Type 2: Complete Binary Tree
A complete binary tree is one where all levels are completely filled except possibly the last, and the last level is filled from left to right with no gaps.
COMPLETE binary tree:
1
/ \
2 3
/ \ /
4 5 6 ← last level filled left-to-right, no gaps ✓
Array: [1, 2, 3, 4, 5, 6]
0 1 2 3 4 5 ← contiguous, no holes ✓
NOT complete (gap in last level):
1
/ \
2 3
/ /
4 6 ← gap at index 3 (node 2 has no right child)
Array would be: [1, 2, 3, 4, _, 6]
↑ hole — NOT complete
WHY COMPLETE TREES ARE USED FOR HEAPS: - Nodes fill array positions 0..n-1 with no holes - No null gaps anywhere in the array - Index arithmetic gives parent/child without pointer traversal - O(1) access to any node by index HEIGHT of a complete tree with n nodes: ⌊log₂(n)⌋ n=1: height 0 n=4: height 2 n=8: height 3
Type 3: Perfect Binary Tree
A perfect binary tree is both full and complete — every internal node has exactly 2 children AND all leaf nodes are at the same level.
PERFECT binary tree:
Level 0: 1 1 node
/ \
Level 1: 2 3 2 nodes
/ \ / \
Level 2: 4 5 6 7 4 nodes
Total: 1 + 2 + 4 = 7 = 2³ - 1 nodes
PERFECT binary trees with h+1 levels:
h=0: 1 node (just root)
h=1: 3 nodes
h=2: 7 nodes
h=3: 15 nodes
h levels: 2^(h+1) - 1 nodes
FORMULA: n = 2^(h+1) - 1 → h = log₂(n+1) - 1
Every level is completely full.
Number of leaves = (n + 1) / 2 = 2^h = exactly half of all nodes.
RELATIONSHIP between the types: PERFECT ⊂ COMPLETE ⊂ BINARY PERFECT ⊂ FULL ⊂ BINARY Perfect → always Full and Complete Complete → not necessarily Full (last level may have nodes with 1 child) Full → not necessarily Complete (shape can be uneven) Venn diagram: ┌─────────────────────────────────────────┐ │ Binary Tree │ │ ┌────────────────────────────────────┐ │ │ │ Full Binary Tree │ │ │ │ ┌──────────────────────────────┐ │ │ │ │ │ Perfect Binary Tree │ │ │ │ │ └──────────────────────────────┘ │ │ │ └────────────────────────────────────┘ │ │ ┌────────────────────────────────────┐ │ │ │ Complete Binary Tree │ │ │ │ (contains Perfect as a subset) │ │ │ └────────────────────────────────────┘ │ └─────────────────────────────────────────┘
Type 4: Balanced Binary Tree
A balanced binary tree is one where the heights of the left and right subtrees of every node differ by at most 1.
BALANCED binary tree:
1 height(left)=2, height(right)=1
/ \ diff = |2-1| = 1 ≤ 1 ✓
2 3
/ \
4 5 At node 2: height(left)=1, height(right)=1, diff=0 ✓
At node 3: height(left)=0, height(right)=0, diff=0 ✓
At node 4: diff=0 ✓ At node 5: diff=0 ✓
NOT balanced:
1 height(left)=3, height(right)=0
\ diff = 3 > 1 ✗
2
\
3
\
4
WHY BALANCE MATTERS:
Balanced tree with n nodes: height = O(log n)
Unbalanced (worst case): height = O(n)
Search in balanced BST: O(log n) ← fast
Search in skewed BST: O(n) ← same as linear scan
AVL trees and Red-Black trees are self-balancing BSTs that
maintain this property automatically after every insert/delete.
CHECKING BALANCE:
A tree is balanced if:
1. Left subtree is balanced
2. Right subtree is balanced
3. |height(left) - height(right)| ≤ 1
All three must hold at EVERY node (not just the root).
1public class BalancedCheck {
2
3 static class TreeNode {
4 int val; TreeNode left, right;
5 TreeNode(int v) { val = v; }
6 }
7
8 // Returns height if balanced, -1 if not balanced
9 public static int checkHeight(TreeNode node) {
10 if (node == null) return 0;
11
12 int leftH = checkHeight(node.left);
13 if (leftH == -1) return -1; // Left subtree unbalanced
14
15 int rightH = checkHeight(node.right);
16 if (rightH == -1) return -1; // Right subtree unbalanced
17
18 if (Math.abs(leftH - rightH) > 1) return -1; // This node unbalanced
19
20 return 1 + Math.max(leftH, rightH); // Height of this subtree
21 }
22
23 public static boolean isBalanced(TreeNode root) {
24 return checkHeight(root) != -1;
25 }
26
27 public static void main(String[] args) {
28 // Balanced tree: 1
29 // / \
30 // 2 3
31 // / \
32 // 4 5
33 TreeNode balanced = new TreeNode(1);
34 balanced.left = new TreeNode(2);
35 balanced.right = new TreeNode(3);
36 balanced.left.left = new TreeNode(4);
37 balanced.left.right = new TreeNode(5);
38 System.out.println("Is balanced: " + isBalanced(balanced)); // true
39
40 // Unbalanced tree: 1
41 // \
42 // 2
43 // \
44 // 3
45 TreeNode unbalanced = new TreeNode(1);
46 unbalanced.right = new TreeNode(2);
47 unbalanced.right.right = new TreeNode(3);
48 System.out.println("Is balanced: " + isBalanced(unbalanced)); // false
49 }
50}Output:
Is balanced: true
Is balanced: false
Type 5: Degenerate (Skewed) Tree
A degenerate tree (or skewed tree) is one where every internal node has only one child. It degenerates into a linked list — losing all the efficiency advantages of a tree.
RIGHT-SKEWED: LEFT-SKEWED:
1 1
\ /
2 2
\ /
3 3
\ /
4 4
Both have HEIGHT = n-1 = 3 for n=4 nodes.
Both are the WORST CASE for all binary tree algorithms.
COMPARISON: balanced vs degenerate for BST operations
Balanced Degenerate
Search: O(log n) ← fast O(n) ← slow
Insert: O(log n) O(n)
Delete: O(log n) O(n)
Height: O(log n) O(n)
WHEN IT OCCURS: inserting already-sorted data into a BST
Insert 1, 2, 3, 4, 5 in order:
1
\
2
\
3
\
4 ← right-skewed tree, height = n-1 = 4
All Types Side by Side
FULL COMPLETE PERFECT BALANCED DEGENERATE
1 1 1 1 1
/ \ / \ / \ / \ \
2 3 2 3 2 3 2 3 2
/ \ / \ / / \ / \ / \ \
4 5 4 5 6 4 5 6 7 4 5 3
Every node Last level All levels Height diff Each node has
has 0 or 2 left-to-right full, all ≤ 1 at exactly 1 child
children no gaps leaves same every node
Used for: Decision trees Heaps Ideal search AVL / R-B trees Worst case BST
Counting Properties Reference
For a PERFECT binary tree with height h: Levels: h + 1 (level 0 through level h) Total nodes: 2^(h+1) - 1 Leaf nodes: 2^h Internal: 2^h - 1 For a COMPLETE binary tree with n nodes: Height: ⌊log₂(n)⌋ Leaf nodes: ⌈n/2⌉ For a FULL binary tree with n nodes (n must be odd): Internal nodes: (n-1)/2 Leaf nodes: (n+1)/2 Relation: L = I + 1 For ANY binary tree with n nodes: Max height: n - 1 (degenerate) Min height: ⌊log₂(n)⌋ (complete/perfect) Max nodes at level k: 2^k Max total nodes for height h: 2^(h+1) - 1
Complexity Summary by Type
| Tree Type | Height | Space | Search | Insert | Notes |
|---|---|---|---|---|---|
| General Binary | O(n) worst | O(n) | O(n) | O(n) | No ordering, no balance |
| Balanced | O(log n) | O(n) | O(log n) | O(log n) | Maintained by AVL/RB trees |
| Complete | O(log n) | O(n) | O(n) | O(log n) | Heap insert is O(log n) |
| Perfect | O(log n) | O(n) | O(n) | — | Cannot maintain after arbitrary insert |
| Degenerate | O(n) | O(n) | O(n) | O(n) | Worst case — linked list |
Common Mistakes
Confusing "full" and "complete". A full binary tree has every node with 0 or 2 children (no single-child nodes). A complete binary tree fills levels left to right (last level may have single-child nodes — specifically the rightmost internal node may have only a left child). These are independent properties — a tree can be full but not complete, complete but not full, both, or neither.
Assuming a balanced tree is always perfect. Balanced means every node's left and right subtree heights differ by at most 1. The tree does not need to be symmetric or have all leaves at the same level. A perfect tree is always balanced, but a balanced tree is not always perfect.
Checking balance only at the root. A tree is balanced only if every node is balanced — the property must hold recursively throughout. A tree with balanced root but an unbalanced grandchild is NOT a balanced binary tree.
Forgetting that a node with one child is valid in a binary tree. The definition says "at most two children" — one child is permitted (just not three or more). Only a full binary tree specifically restricts nodes to 0 or 2 children.
Interview Questions
Q: What is the difference between a full, complete, and perfect binary tree?
A full binary tree has every node with exactly 0 or 2 children — no single-child nodes. A complete binary tree fills all levels top-to-bottom, left-to-right with no gaps — the last level may be partially filled but only from the left. A perfect binary tree is both full and complete — all internal nodes have exactly 2 children and all leaves are at the same level. Perfect ⊂ Complete and Perfect ⊂ Full, but Complete and Full are independent properties.
Q: Why is a complete binary tree used as the underlying structure for a heap?
A complete binary tree guarantees no gaps in the array when stored using index arithmetic. With nodes at positions 0 through n-1 in a contiguous array, the parent/child relationships are computed directly: parent at (i-1)/2, left child at 2i+1, right child at 2i+2. This means no pointers are needed — the entire tree lives in a flat array with O(1) access to any node. The completeness property ensures every insertion (at the end of the array) maintains the tree's shape without creating holes.
Q: What is the minimum and maximum height of a binary tree with n nodes?
Minimum height: ⌊log₂(n)⌋ — achieved by a complete or perfect binary tree that packs nodes as compactly as possible. Maximum height: n−1 — achieved by a degenerate (skewed) tree where every node has exactly one child, forming a chain. The ratio between minimum and maximum height is the difference between O(log n) and O(n) algorithm performance — the motivation for self-balancing trees.
FAQs
Can a binary tree have zero nodes?
Yes — an empty tree (null root) is a valid binary tree with 0 nodes and height −1 (by convention). This is the base case for most recursive tree algorithms: if node is None: return.
Is a single node a valid binary tree?
Yes — a single node (the root) with no children is a valid binary tree. It is simultaneously a full binary tree (every node has 0 or 2 children — the root has 0), a complete binary tree, a perfect binary tree, and a balanced binary tree. Height = 0.
How many distinct binary trees can be formed with n nodes?
The number of structurally distinct binary trees with n nodes is the nth Catalan number: C(n) = (2n choose n) / (n+1). For n=3: C(3) = 5. For n=4: C(4) = 14. This grows as O(4ⁿ / n^(3/2)), meaning the number of possible shapes grows extremely fast.
Summary
A binary tree is a tree where every node has at most two children (left and right). The node structure is the same across all variants: val, left, right.
Five structural types:
- ›Full — every node has 0 or 2 children;
L = I + 1 - ›Complete — filled left to right, no gaps; maps directly to an array; used for heaps
- ›Perfect — all levels full, all leaves at same level;
n = 2^(h+1) - 1 - ›Balanced — height difference ≤ 1 at every node; guarantees O(log n) height
- ›Degenerate — every node has one child; height = n−1; same as a linked list
Two memory representations:
- ›Linked nodes — most common; each node is a heap-allocated object with left/right pointers
- ›Array — for complete trees only; parent at
(i-1)/2, left at2i+1, right at2i+2
Key height bounds for n nodes:
- ›Minimum: ⌊log₂(n)⌋ (complete/perfect)
- ›Maximum: n−1 (degenerate)
In the next topic you will explore Binary Tree Traversals — the four fundamental ways to visit every node: preorder, inorder, postorder, and level order, each with recursive and iterative implementations.
What is the maximum number of nodes at level k of a binary tree (root is level 0)?