Binary Trees - Learning Module

Loading content...

0/276

Node-Based Representation in Code

From Theory to Implementation

We've built the conceptual foundation: binary trees have at most two children per node, left and right are semantically distinct, and the recursive structure enables elegant algorithms. Now it's time to translate these concepts into actual, working code.

Implementing binary trees requires making concrete decisions that theory abstracts away: How do we allocate memory for nodes? How do we represent the absence of a child? How do we build trees from data? What utility methods should every tree class include?

This page answers these questions comprehensively, providing production-ready implementation patterns that you'll use throughout your career.

What You Will Learn

You'll understand the standard node-based representation of binary trees, including class/struct design, null handling, tree construction techniques, and common utility methods. You'll also see alternative representations (like arrays for complete trees) and understand when each is appropriate.

The Node Class Design

The fundamental building block of any binary tree implementation is the node class (or struct in languages like C). A well-designed node class is simple yet flexible, supporting the operations we need while remaining efficient.

Essential components of a binary tree node:

Value/Data: The payload stored at this node
Left Reference: Pointer/reference to the left child (null if absent)
Right Reference: Pointer/reference to the right child (null if absent)

Optional additions:

Parent Reference: Pointer to parent node (trades memory for convenience)
Metadata: Size of subtree, height, balance factor, etc. (for special tree types)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Generic binary tree node with minimal footprint.
 * The generic type T allows storing any kind of value.
 */
class TreeNode<T> {
    value: T;
    left: TreeNode<T> | null;
    right: TreeNode<T> | null;
    
    constructor(value: T) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
    
    // Convenience method: check if this is a leaf node
    isLeaf(): boolean {
        return this.left === null && this.right === null;
    }
    
    // Convenience method: check if node has both children
    hasBothChildren(): boolean {
        return this.left !== null && this.right !== null;
    }
    
    // Convenience method: count of children (0, 1, or 2)
    childCount(): number {
        return (this.left !== null ? 1 : 0) + (this.right !== null ? 1 : 0);
    }
}
 
// Usage examples:
const root = new TreeNode<number>(10);
root.left = new TreeNode<number>(5);
root.right = new TreeNode<number>(15);
root.left.left = new TreeNode<number>(3);
root.left.right = new TreeNode<number>(7);
 
console.log(root.isLeaf());           // false
console.log(root.left.left.isLeaf()); // true
console.log(root.childCount());       // 2
console.log(root.left.childCount());  // 2
console.log(root.right.childCount()); // 0

Design considerations:

Immutability vs Mutability:

The example above uses mutable nodes—we can modify left and right after construction. This is standard for most use cases. For functional programming or concurrent scenarios, consider immutable nodes:

class ImmutableTreeNode<T> {
    readonly value: T;
    readonly left: ImmutableTreeNode<T> | null;
    readonly right: ImmutableTreeNode<T> | null;
    
    constructor(
        value: T,
        left: ImmutableTreeNode<T> | null = null,
        right: ImmutableTreeNode<T> | null = null
    ) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
    
    // 'Modifications' return new nodes
    withLeft(left: ImmutableTreeNode<T> | null): ImmutableTreeNode<T> {
        return new ImmutableTreeNode(this.value, left, this.right);
    }
}

Immutable nodes enable structural sharing and are safer in concurrent programs, but incur allocation overhead for modifications.

Memory Layout Matters

In languages like C/C++, the node layout affects cache performance. Keeping nodes compact (just value + two pointers) improves cache utilization. Adding parent pointers or metadata increases node size and can hurt performance for large trees.

Representing Null/Empty Children

When a node lacks a left or right child, we need to represent this absence. Different languages and approaches handle this differently:

Approach 1: Native Null (Most Common)

Most languages use their native null/nil/None value:

// TypeScript/JavaScript
left: TreeNode<T> | null = null;

// Java
TreeNode left = null;

// Python
self.left = None

// C++
TreeNode* left = nullptr;

Approach 2: Optional/Maybe Types

Functional languages often use explicit optional types:

-- Haskell
data Tree a = Empty | Node a (Tree a) (Tree a)

-- Rust
left: Option<Box<TreeNode<T>>>

Approach 3: Sentinel Node

Some implementations use a dedicated 'sentinel' or 'NIL' node instead of null:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * Sentinel-based binary tree node.
 * All 'null' positions point to a special NIL node.
 * Used in Red-Black tree implementations.
 */
class SentinelTreeNode<T> {
    value: T | null;
    left: SentinelTreeNode<T>;
    right: SentinelTreeNode<T>;
    
    // The global sentinel - represents all null positions
    private static readonly _NIL: SentinelTreeNode<any> = (() => {
        const nil = Object.create(SentinelTreeNode.prototype);
        nil.value = null;
        nil.left = nil;   // NIL's children are NIL itself
        nil.right = nil;
        return nil;
    })();
    
    static NIL<T>(): SentinelTreeNode<T> {
        return SentinelTreeNode._NIL;
    }
    
    constructor(value: T) {
        this.value = value;
        this.left = SentinelTreeNode.NIL();
        this.right = SentinelTreeNode.NIL();
    }
    
    isNil(): boolean {
        return this === SentinelTreeNode._NIL;
    }
}
 
// Usage - no null checks, just isNil() checks
function countNodes<T>(node: SentinelTreeNode<T>): number {
    if (node.isNil()) return 0;
    return 1 + countNodes(node.left) + countNodes(node.right);
}
 
// Advantages of sentinel approach:
// - No null pointer exceptions possible
// - Simplifies some algorithms (rotations in Red-Black trees)
// - node.left is always valid (never null)
//
// Disadvantages:
// - Extra memory for NIL node
// - isNil() check instead of null check
// - Less conventional, may confuse others

Null Representation Approaches
Approach	Pros	Cons	Use When
Native null	Universal, zero overhead, familiar	Null pointer errors possible	General purpose, most implementations
Optional types	Type-safe, explicit emptiness	More verbose, language support needed	Rust, Haskell, when safety is paramount
Sentinel node	No null checks, simpler rotations	Extra memory, unconventional	Red-Black trees, when simplifying algorithms

Defensive Programming

Regardless of null representation, always handle the empty case first in recursive functions. The pattern 'if (node === null) return defaultValue;' as the first line prevents null pointer errors and establishes a clear base case.

Building Trees from Data

Trees rarely exist in isolation—we usually construct them from input data. Let's explore common tree construction patterns:

Pattern 1: Manual Construction

For small trees or tests, build nodes directly:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// Building tree:
//        1
//       / \
//      2   3
//     / \
//    4   5
 
// Approach 1: Bottom-up construction
const node4 = new TreeNode(4);
const node5 = new TreeNode(5);
const node2 = new TreeNode(2);
node2.left = node4;
node2.right = node5;
const node3 = new TreeNode(3);
const node1 = new TreeNode(1);
node1.left = node2;
node1.right = node3;
 
// Approach 2: Inline construction (more concise)
function buildSampleTree(): TreeNode<number> {
    const root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(3);
    root.left.left = new TreeNode(4);
    root.left.right = new TreeNode(5);
    return root;
}
 
// Approach 3: Factory function with children
function createNode<T>(
    value: T,
    left?: TreeNode<T> | null,
    right?: TreeNode<T> | null
): TreeNode<T> {
    const node = new TreeNode(value);
    node.left = left ?? null;
    node.right = right ?? null;
    return node;
}
 
// Clean nested construction:
const tree = createNode(1,
    createNode(2,
        createNode(4),
        createNode(5)
    ),
    createNode(3)
);

Pattern 2: Building from Level-Order Array

A common representation for trees in coding problems uses level-order arrays with null markers:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
 * Build a binary tree from a level-order array.
 * Null values indicate missing nodes.
 * 
 * Example: [1, 2, 3, null, 4, null, 5]
 * Produces:
 *       1
 *      / \
 *     2   3
 *      \   \
 *       4   5
 */
function buildFromLevelOrder(values: (number | null)[]): TreeNode<number> | null {
    if (values.length === 0 || values[0] === null) {
        return null;
    }
    
    const root = new TreeNode(values[0]);
    const queue: TreeNode<number>[] = [root];
    let i = 1;
    
    while (queue.length > 0 && i < values.length) {
        const current = queue.shift()!;
        
        // Process left child
        if (i < values.length) {
            if (values[i] !== null) {
                current.left = new TreeNode(values[i]!);
                queue.push(current.left);
            }
            i++;
        }
        
        // Process right child
        if (i < values.length) {
            if (values[i] !== null) {
                current.right = new TreeNode(values[i]!);
                queue.push(current.right);
            }
            i++;
        }
    }
    
    return root;
}
 
// Usage examples:
const balanced = buildFromLevelOrder([1, 2, 3, 4, 5, 6, 7]);
//       1
//      / \
//     2   3
//    / \ / \
//   4  5 6  7
 
const skewed = buildFromLevelOrder([1, 2, null, 3, null, 4]);
//     1
//    /
//   2
//  /
// 3
///
//4

Pattern 3: Building from Sorted Array (BST)

To create a balanced BST from a sorted array, use divide-and-conquer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Build a height-balanced BST from a sorted array.
 * Uses the middle element as root to ensure balance.
 */
function sortedArrayToBST(nums: number[]): TreeNode<number> | null {
    function buildBST(left: number, right: number): TreeNode<number> | null {
        if (left > right) {
            return null;  // Base case: empty range
        }
        
        // Choose middle element as root for balance
        const mid = Math.floor((left + right) / 2);
        const node = new TreeNode(nums[mid]);
        
        // Recursively build left and right subtrees
        node.left = buildBST(left, mid - 1);
        node.right = buildBST(mid + 1, right);
        
        return node;
    }
    
    return buildBST(0, nums.length - 1);
}
 
// Example: [1, 2, 3, 4, 5, 6, 7]
// Produces balanced BST:
//        4
//       / \
//      2   6
//     / \ / \
//    1  3 5  7
//
// Height: 2 (optimal for 7 nodes)

Construction Determines Balance

How you build a BST dramatically affects its shape. Inserting sorted values one-by-one creates a degenerate tree (linked list). Using the middle-element-as-root strategy produces a balanced tree. Always consider construction order for BSTs.

The Tree Class Wrapper

While nodes are the building blocks, it's often useful to wrap the tree in a class that provides a cleaner API and manages the root reference:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
/**
 * Binary Tree wrapper class.
 * Encapsulates the root and provides tree-level operations.
 */
class BinaryTree<T> {
    private root: TreeNode<T> | null = null;
    
    constructor(rootValue?: T) {
        if (rootValue !== undefined) {
            this.root = new TreeNode(rootValue);
        }
    }
    
    // Factory method: create from level-order array
    static fromLevelOrder(values: (number | null)[]): BinaryTree<number> {
        const tree = new BinaryTree<number>();
        tree.root = buildFromLevelOrder(values);
        return tree;
    }
    
    // Check if tree is empty
    isEmpty(): boolean {
        return this.root === null;
    }
    
    // Get the root (for algorithms that need direct access)
    getRoot(): TreeNode<T> | null {
        return this.root;
    }
    
    // Count total nodes
    size(): number {
        return this.countNodes(this.root);
    }
    
    private countNodes(node: TreeNode<T> | null): number {
        if (node === null) return 0;
        return 1 + this.countNodes(node.left) + this.countNodes(node.right);
    }
    
    // Calculate tree height
    height(): number {
        return this.calculateHeight(this.root);
    }
    
    private calculateHeight(node: TreeNode<T> | null): number {
        if (node === null) return -1;  // Convention: empty tree has height -1
        return 1 + Math.max(
            this.calculateHeight(node.left),
            this.calculateHeight(node.right)
        );
    }
    
    // Traversals
    inorder(): T[] {
        const result: T[] = [];
        this.inorderHelper(this.root, result);
        return result;
    }
    
    private inorderHelper(node: TreeNode<T> | null, result: T[]): void {
        if (node === null) return;
        this.inorderHelper(node.left, result);
        result.push(node.value);
        this.inorderHelper(node.right, result);
    }
    
    preorder(): T[] {
        const result: T[] = [];
        this.preorderHelper(this.root, result);
        return result;
    }
    
    private preorderHelper(node: TreeNode<T> | null, result: T[]): void {
        if (node === null) return;
        result.push(node.value);
        this.preorderHelper(node.left, result);
        this.preorderHelper(node.right, result);
    }
    
    postorder(): T[] {
        const result: T[] = [];
        this.postorderHelper(this.root, result);
        return result;
    }
    
    private postorderHelper(node: TreeNode<T> | null, result: T[]): void {
        if (node === null) return;
        this.postorderHelper(node.left, result);
        this.postorderHelper(node.right, result);
        result.push(node.value);
    }
    
    levelOrder(): T[] {
        if (this.root === null) return [];
        
        const result: T[] = [];
        const queue: TreeNode<T>[] = [this.root];
        
        while (queue.length > 0) {
            const node = queue.shift()!;
            result.push(node.value);
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        return result;
    }
    
    // Utility: Print tree structure (for debugging)
    print(): void {
        this.printHelper(this.root, "", true);
    }
    
    private printHelper(node: TreeNode<T> | null, prefix: string, isLeft: boolean): void {
        if (node === null) return;
        
        console.log(prefix + (isLeft ? "├── " : "└── ") + node.value);
        
        this.printHelper(node.left, prefix + (isLeft ? "│   " : "    "), true);
        this.printHelper(node.right, prefix + (isLeft ? "│   " : "    "), false);
    }
}
 
// Usage:
const tree = BinaryTree.fromLevelOrder([1, 2, 3, 4, 5, 6, 7]);
console.log("Size:", tree.size());           // 7
console.log("Height:", tree.height());       // 2
console.log("Inorder:", tree.inorder());     // [4, 2, 5, 1, 6, 3, 7]
console.log("Preorder:", tree.preorder());   // [1, 2, 4, 5, 3, 6, 7]
console.log("Postorder:", tree.postorder()); // [4, 5, 2, 6, 7, 3, 1]
tree.print();

Encapsulation vs Direct Access

The wrapper class encapsulates tree operations but sometimes you need direct node access for complex algorithms. The getRoot() method provides this escape hatch. For interview problems, often you'll work directly with TreeNode; for production code, a wrapper class provides a cleaner API.

Array-Based Representation

For complete binary trees, there's an elegant alternative to pointer-based nodes: store the tree directly in an array using implicit indexing.

The indexing scheme:

For a node at index i (0-indexed):

Left child: 2*i + 1
Right child: 2*i + 2
Parent: ⌊(i - 1) / 2⌋

This works because complete trees have no 'gaps'—all levels are filled left-to-right.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
/**
 * Array-based complete binary tree.
 * Primarily used for heaps where completeness is guaranteed.
 */
class ArrayBinaryTree<T> {
    private data: T[] = [];
    
    // Index calculations
    private leftChild(i: number): number { return 2 * i + 1; }
    private rightChild(i: number): number { return 2 * i + 2; }
    private parent(i: number): number { return Math.floor((i - 1) / 2); }
    
    // Check if index has left/right child
    private hasLeft(i: number): boolean { return this.leftChild(i) < this.data.length; }
    private hasRight(i: number): boolean { return this.rightChild(i) < this.data.length; }
    
    // Insert at next available position (maintains completeness)
    insert(value: T): void {
        this.data.push(value);
    }
    
    // Get value at index
    get(i: number): T | undefined {
        return this.data[i];
    }
    
    // Get left child value
    getLeftChild(i: number): T | undefined {
        if (!this.hasLeft(i)) return undefined;
        return this.data[this.leftChild(i)];
    }
    
    // Get right child value
    getRightChild(i: number): T | undefined {
        if (!this.hasRight(i)) return undefined;
        return this.data[this.rightChild(i)];
    }
    
    // Get parent value
    getParent(i: number): T | undefined {
        if (i === 0) return undefined;  // Root has no parent
        return this.data[this.parent(i)];
    }
    
    // Level-order traversal (just the array!)
    levelOrder(): T[] {
        return [...this.data];
    }
    
    // Inorder traversal (recursive using indices)
    inorder(): T[] {
        const result: T[] = [];
        this.inorderHelper(0, result);
        return result;
    }
    
    private inorderHelper(i: number, result: T[]): void {
        if (i >= this.data.length) return;
        this.inorderHelper(this.leftChild(i), result);
        result.push(this.data[i]);
        this.inorderHelper(this.rightChild(i), result);
    }
    
    // Visualize the tree structure
    print(): void {
        if (this.data.length === 0) {
            console.log("(empty)");
            return;
        }
        
        let level = 0;
        let levelStart = 0;
        let levelSize = 1;
        
        while (levelStart < this.data.length) {
            const levelEnd = Math.min(levelStart + levelSize, this.data.length);
            const values = this.data.slice(levelStart, levelEnd);
            console.log(`Level ${level}: ${values.join(' ')}`);
            
            levelStart = levelEnd;
            levelSize *= 2;
            level++;
        }
    }
}
 
// Example:
//        10
//       /  \
//      5    15
//     / \  /
//    3   7 12
//
// Array: [10, 5, 15, 3, 7, 12]
//         0   1   2  3  4   5
 
const arrayTree = new ArrayBinaryTree<number>();
[10, 5, 15, 3, 7, 12].forEach(v => arrayTree.insert(v));
 
console.log(arrayTree.get(0));           // 10 (root)
console.log(arrayTree.getLeftChild(0));  // 5
console.log(arrayTree.getRightChild(0)); // 15
console.log(arrayTree.getParent(5));     // 15 (parent of index 5)
console.log(arrayTree.inorder());        // [3, 5, 7, 10, 12, 15]

Pointer-Based vs Array-Based Representation
Aspect	Pointer-Based	Array-Based
Memory usage	Node overhead (pointers per node)	Compact (just values)
Cache performance	Nodes scattered in memory	Contiguous, cache-friendly
Flexibility	Any shape tree	Complete trees only
Insertion/deletion	Flexible positions	Only at 'end' (fill order)
Navigation	Follow pointers	Index arithmetic
Primary use	General binary trees, BSTs	Heaps, priority queues

Array Representation Has Constraints

Array representation only works well for complete binary trees. For sparse or unbalanced trees, the array would have many empty slots, wasting memory. Heaps are the classic use case because the heap property maintenance naturally preserves completeness.

When to Use Parent Pointers

Adding a parent reference to each node is a common enhancement that trades memory for algorithmic convenience:

With parent pointers:

Navigate upward without recursion or a stack
Find ancestors directly
Simplify some tree modifications (like successor finding in BSTs)

Without parent pointers:

Less memory per node
Must use recursion or stack to track the path
Updates simpler (no parent maintenance)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/**
 * Binary tree node with parent reference.
 * Enables upward navigation without stack/recursion.
 */
class ParentAwareNode<T> {
    value: T;
    left: ParentAwareNode<T> | null = null;
    right: ParentAwareNode<T> | null = null;
    parent: ParentAwareNode<T> | null = null;
    
    constructor(value: T) {
        this.value = value;
    }
    
    // Set left child and maintain parent link
    setLeft(child: ParentAwareNode<T> | null): void {
        this.left = child;
        if (child) child.parent = this;
    }
    
    // Set right child and maintain parent link
    setRight(child: ParentAwareNode<T> | null): void {
        this.right = child;
        if (child) child.parent = this;
    }
    
    // Check if this is the root
    isRoot(): boolean {
        return this.parent === null;
    }
    
    // Check if this is a left child of its parent
    isLeftChild(): boolean {
        return this.parent !== null && this.parent.left === this;
    }
    
    // Get the sibling (if any)
    getSibling(): ParentAwareNode<T> | null {
        if (this.parent === null) return null;
        return this.isLeftChild() ? this.parent.right : this.parent.left;
    }
    
    // Get depth (distance from root) - O(depth) with parent pointers
    getDepth(): number {
        let depth = 0;
        let current: ParentAwareNode<T> | null = this;
        while (current.parent !== null) {
            depth++;
            current = current.parent;
        }
        return depth;
    }
    
    // Find lowest common ancestor with another node
    lowestCommonAncestor(other: ParentAwareNode<T>): ParentAwareNode<T> | null {
        const ancestors = new Set<ParentAwareNode<T>>();
        
        // Collect all ancestors of this node
        let current: ParentAwareNode<T> | null = this;
        while (current !== null) {
            ancestors.add(current);
            current = current.parent;
        }
        
        // Find first ancestor of other that's in the set
        current = other;
        while (current !== null) {
            if (ancestors.has(current)) return current;
            current = current.parent;
        }
        
        return null;  // Nodes not in same tree
    }
}
 
// Usage example:
const root = new ParentAwareNode(1);
const left = new ParentAwareNode(2);
const right = new ParentAwareNode(3);
const leftLeft = new ParentAwareNode(4);
 
root.setLeft(left);
root.setRight(right);
left.setLeft(leftLeft);
 
console.log(leftLeft.getDepth());        // 2
console.log(leftLeft.isLeftChild());     // true
console.log(left.getSibling()?.value);   // 3
console.log(leftLeft.parent?.value);     // 2

When parent pointers are valuable:

Iterator implementations: Moving to 'next' node in inorder sequence requires going up
Finding successors/predecessors in BSTs: Inorder successor may require going to parent
Lowest common ancestor queries: Can traverse upward from both nodes
Tree modifications: Rotations in balanced trees (AVL, Red-Black)
Path problems: Finding path between two nodes

When to avoid parent pointers:

Memory-constrained environments: Extra pointer per node adds up
Simple recursive algorithms: Recursion naturally tracks the path
Immutable trees: Parent pointers create circular references, problematic for immutable designs

Maintenance Burden

Parent pointers require careful maintenance. Every insertion, deletion, and rotation must update parent references. Use setter methods (like setLeft/setRight above) to ensure consistency. A common bug is setting left/right without updating the child's parent pointer.

Implementation Across Languages

Binary tree implementation details vary across programming languages. Here's how the same concepts manifest in different environments:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Java: Class-based with explicit types
public class TreeNode<T> {
    public T value;
    public TreeNode<T> left;
    public TreeNode<T> right;
    
    public TreeNode(T value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}
 
// For LeetCode-style problems (typically):
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Python: Clean, dynamic typing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
# With type hints (Python 3.9+)
from __future__ import annotations
from typing import Optional
 
class TreeNode:
    def __init__(
        self, 
        val: int = 0, 
        left: Optional[TreeNode] = None, 
        right: Optional[TreeNode] = None
    ):
        self.val = val
        self.left = left
        self.right = right

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// C++: Struct-based with pointers
template<typename T>
struct TreeNode {
    T value;
    TreeNode<T>* left;
    TreeNode<T>* right;
    
    TreeNode(T val) : value(val), left(nullptr), right(nullptr) {}
    
    // Destructor for proper cleanup
    ~TreeNode() {
        delete left;
        delete right;
    }
};
 
// Modern C++ with smart pointers (recommended)
#include <memory>
 
template<typename T>
struct TreeNode {
    T value;
    std::unique_ptr<TreeNode<T>> left;
    std::unique_ptr<TreeNode<T>> right;
    
    TreeNode(T val) : value(val), left(nullptr), right(nullptr) {}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Rust: Ownership-aware with Box for heap allocation
pub struct TreeNode<T> {
    pub value: T,
    pub left: Option<Box<TreeNode<T>>>,
    pub right: Option<Box<TreeNode<T>>>,
}
 
impl<T> TreeNode<T> {
    pub fn new(value: T) -> Self {
        TreeNode {
            value,
            left: None,
            right: None,
        }
    }
    
    pub fn with_children(
        value: T, 
        left: Option<Box<TreeNode<T>>>,
        right: Option<Box<TreeNode<T>>>
    ) -> Self {
        TreeNode { value, left, right }
    }
}

Language Idioms Matter

Each language has its idioms for null handling (None in Python, nullptr in C++, Option in Rust), memory management (garbage collection vs manual vs ownership), and type systems. Adapt the core concepts to your language's conventions rather than translating literally.

Summary: Binary Trees in Code

We've covered the complete journey from abstract binary tree concept to concrete implementation. Let's consolidate the key implementation patterns:

Key Implementation Takeaways

•The node class contains value, left, and right — This minimal structure supports all binary tree operations
•Null represents absent children — Use your language's native null with explicit type annotations (TreeNode | null)
•Build trees bottom-up or from traversal arrays — Different construction methods suit different use cases
•Wrapper classes provide clean APIs — Encapsulate root and expose tree-level operations
•Array representation suits complete trees — Use for heaps; index formulas replace pointer navigation
•Parent pointers trade memory for convenience — Add when upward navigation is frequent
•Adapt to language idioms — Use Python's Optional, Rust's Option<Box<>>, C++'s smart pointers as appropriate

The foundation is complete:

With this module, you've mastered binary tree fundamentals:

What binary trees are and why the binary constraint is powerful
How left and right children carry semantic meaning
How to implement binary trees in production code

You're now ready to explore what we can DO with binary trees: traversals, recursive algorithms, and the powerful specializations like binary search trees and heaps.

Module Complete

You now possess a comprehensive understanding of binary tree structure and representation. From the conceptual definition to working code, you can create, manipulate, and reason about binary trees. This foundation supports everything that follows—from tree traversals to BSTs to balanced trees.