Binary Trees - Learning Module

Loading content...

0/276

Left and Right Child Distinction

Position with Meaning

In a general tree, children are simply a collection—first child, second child, third child. The numbers are arbitrary; swapping the second and third child doesn't change the tree's meaning. But in a binary tree, something fundamentally different happens.

The left child is not the same as the right child. Swapping them creates a different tree. This isn't just a positional convention—it's a semantic distinction that enables some of the most powerful data structures in computer science.

This page explores why left and right matter, how this distinction encodes information, and what it makes possible.

What You Will Learn

You'll understand the semantic difference between left and right children, how this distinction enables ordering in binary search trees, its role in tree traversals, and how it influences expression tree interpretation. By the end, you'll see left/right not as arbitrary labels but as carriers of meaning.

Ordered vs Unordered Children

Let's make the distinction crystal clear with an example.

In a general tree (unordered children):

    Parent A                Parent A
      / \                     / \
     B   C        SAME AS    C   B

If children are just a collection {B, C}, then ordering doesn't matter. These are the same tree.

In a binary tree (ordered children):

    Tree X                  Tree Y
      A                       A
     / \                     / \
    B   C        ≠          C   B
   (left)(right)         (left)(right)

These are different binary trees. In Tree X, B is the left child and C is the right child. In Tree Y, the positions are reversed. The parent-child relationships are identical, but the left/right designation differs.

Why Does This Matter?

The left/right distinction carries semantic weight. In a Binary Search Tree, left means 'values smaller than parent' and right means 'values larger than parent.' In an expression tree, left/right matter for non-commutative operations like subtraction and division. The position encodes information.

Formal terminology:

Left child: The root of the left subtree of a node
Right child: The root of the right subtree of a node
Left descendant: Any node in the left subtree
Right descendant: Any node in the right subtree
Left spine: The path of nodes formed by always going left from the root
Right spine: The path of nodes formed by always going right from the root

These terms wouldn't exist if left and right were interchangeable. We name them because they represent distinct concepts.

Left/Right in Binary Search Trees

The most important application of the left/right distinction is the Binary Search Tree (BST). In a BST, the position of a value encodes its ordering relationship:

The BST Property:

For every node N in the tree:

All values in N's left subtree are less than N's value

All values in N's right subtree are greater than N's value

This property transforms the tree into a searchable structure. Given a value to find, we know exactly which direction to go at each node:

If target < current: go left
If target > current: go right
If target = current: found

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
// The BST search algorithm relies on left/right having meaning
interface BSTNode {
    value: number;
    left: BSTNode | null;
    right: BSTNode | null;
}
 
function bstSearch(node: BSTNode | null, target: number): boolean {
    if (node === null) {
        return false;  // Not found - reached empty subtree
    }
    
    if (target === node.value) {
        return true;   // Found!
    } else if (target < node.value) {
        // Target is smaller → must be in LEFT subtree
        // This is where left/right distinction matters!
        return bstSearch(node.left, target);
    } else {
        // Target is larger → must be in RIGHT subtree
        return bstSearch(node.right, target);
    }
}
 
// Example BST:
//           8
//         /   \
//        3     10
//       / \      \
//      1   6      14
//         / \    /
//        4   7  13
 
// Searching for 7:
// 8: target 7 < 8, go LEFT
// 3: target 7 > 3, go RIGHT  
// 6: target 7 > 6, go RIGHT
// 7: target 7 = 7, FOUND!
 
// Only 4 comparisons to find among 9 nodes (O(log n) behavior)

Why this works:

The left/right distinction lets us eliminate half the tree with each comparison. When we go left, we completely ignore the right subtree—we know the target can't be there. This halving at each step produces O(log n) efficiency.

Without the left/right ordering, we'd have to search both children when the target doesn't match, regressing to O(n) performance. The semantic meaning of 'left' and 'right' is what makes efficient search possible.

The mirror tree problem:

If we 'mirror' a BST (swap all left and right children), we get a valid tree but with reversed ordering:

   Original BST           Mirrored (NOT a valid BST)
       5                        5
      / \                      / \
     3   7       →            7   3
    / \   \                  /   / \
   1   4   9                9   4   1

 Small values left        Large values left
 Large values right       Small values right

The mirrored version violates the BST property because left/right have switched their semantic meaning.

Consistency is Critical

The BST property requires consistent interpretation of left (smaller) and right (larger) throughout the entire tree. Mixing conventions within a tree destroys the search property. Once you choose a convention, it must be maintained.

Left/Right in Tree Traversals

Tree traversal algorithms visit every node exactly once. The order in which they visit nodes depends critically on how they handle left vs. right children.

The classic traversal orders:

Preorder: Visit node, then left subtree, then right subtree
- Notation: N-L-R (Node first)
Inorder: Visit left subtree, then node, then right subtree
- Notation: L-N-R (Node in middle)
Postorder: Visit left subtree, then right subtree, then node
- Notation: L-R-N (Node last)

Notice that left always comes before right in these definitions. This is not arbitrary—it's a convention that produces consistent, predictable behavior.

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
interface TreeNode {
    value: string;
    left: TreeNode | null;
    right: TreeNode | null;
}
 
// Example tree:
//         A
//        / \
//       B   C
//      / \   \
//     D   E   F
 
function preorder(node: TreeNode | null): string[] {
    if (!node) return [];
    return [node.value, ...preorder(node.left), ...preorder(node.right)];
}
// Result: [A, B, D, E, C, F]
// Pattern: Process current, then go deep left, then go deep right
 
function inorder(node: TreeNode | null): string[] {
    if (!node) return [];
    return [...inorder(node.left), node.value, ...inorder(node.right)];
}
// Result: [D, B, E, A, C, F]
// Pattern: Go deep left first, process current, then go deep right
 
function postorder(node: TreeNode | null): string[] {
    if (!node) return [];
    return [...postorder(node.left), ...postorder(node.right), node.value];
}
// Result: [D, E, B, F, C, A]
// Pattern: Go deep left, go deep right, then process current
 
// If we swapped left/right in our tree, all traversal outputs would change!

Why inorder traversal of a BST produces sorted output:

This is a beautiful consequence of the left/right distinction:

Inorder visits: left subtree → current node → right subtree
In a BST: left subtree has smaller values, right subtree has larger values
Therefore: smaller values printed → current value → larger values printed
Result: sorted order!

    BST:          Inorder Traversal:
       5           1 → 3 → 4 → 5 → 7 → 9
      / \
     3   7        Left subtree [1,3,4], then 5, then right subtree [7,9]
    / \   \       Result: [1,3,4,5,7,9] - perfectly sorted!
   1   4   9

This property—that inorder traversal of a BST yields sorted output—is why the left/right distinction isn't just structural but semantically critical.

Traversal Order as Specification

Many tree problems are really asking: 'What order should I process nodes?' Choosing preorder, inorder, or postorder—and remembering that left comes before right—is often the key insight. For BSTs, inorder gives sorted order; for expression trees, postorder gives evaluation order.

Left/Right in Expression Trees

Expression trees represent mathematical expressions as binary trees. Each internal node is an operator; each leaf is an operand. The left/right distinction is crucial for non-commutative operations.

For commutative operations (addition, multiplication):

       +                   +
      / \       SAME AS   / \
     3   5               5   3

   3 + 5 = 5 + 3 = 8

Swapping left and right doesn't change the result.

For non-commutative operations (subtraction, division):

       -                   -
      / \     DIFFERENT   / \
     7   2       FROM    2   7

   7 - 2 = 5     vs.    2 - 7 = -5

Swapping left and right changes the result. The left child is the minuend (what we subtract from), and the right child is the subtrahend (what we subtract).

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
type Operator = '+' | '-' | '*' | '/';
 
interface ExpressionNode {
    type: 'number' | 'operator';
    value?: number;
    operator?: Operator;
    left?: ExpressionNode;
    right?: ExpressionNode;
}
 
function evaluate(node: ExpressionNode): number {
    if (node.type === 'number') {
        return node.value!;
    }
    
    // Operator node: evaluate left and right subtrees
    // ORDER MATTERS for - and /
    const leftValue = evaluate(node.left!);
    const rightValue = evaluate(node.right!);
    
    switch (node.operator) {
        case '+': return leftValue + rightValue;
        case '-': return leftValue - rightValue;  // left MINUS right
        case '*': return leftValue * rightValue;
        case '/': return leftValue / rightValue;  // left DIVIDED BY right
        default: throw new Error('Unknown operator');
    }
}
 
// Expression: (6 + 2) * (10 - 3)
//
//          *
//         / \
//        +   -
//       / \ / \
//      6  2 10 3
//
// Evaluation:
// Left subtree: 6 + 2 = 8
// Right subtree: 10 - 3 = 7
// Root: 8 * 7 = 56
//
// If we swapped left/right of the '-' node:
// Right subtree would be: 3 - 10 = -7
// Root would be: 8 * (-7) = -56
// Completely different result!

Order of operands encoded in structure:

When a compiler parses the expression 10 - 3 * 2, it must:

Recognize operator precedence (* before -)
Build the correct tree structure
Preserve operand order using left/right

Expression: 10 - 3 * 2

Incorrect tree:        Correct tree:
       -                    -
      / \                  / \
     *   2               10   *
    / \                      / \
   10  3                    3   2

Evaluates incorrectly  Evaluates correctly to 4

The left/right positions encode which operand comes first, preserving the original expression's semantics.

Traversals and Expression Notation

Different traversals of an expression tree produce different notations: Inorder gives infix (1 + 2), Preorder gives prefix/Polish (+ 1 2), and Postorder gives postfix/RPN (1 2 +). The left/right distinction is preserved in all notations, determining operand order.

Structural Implications

The left/right distinction affects how we analyze and describe tree structure.

Describing node positions:

We can describe any node's position using a path from the root:

'Left-Left-Right' means: from root, go left, go left, go right
This path uniquely identifies a node in the tree
The path can be encoded as a binary string: 'LLR' = 001 (L=0, R=1)

           A (root)
          / \
         B   C
        / \
       D   E
      /
     F

Path to F: "LLL" = 000
Path to E: "LR" = 01
Path to C: "R" = 1

Implicit positions in complete binary trees:

For complete binary trees stored in arrays, node positions are computed using left/right relationships:

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
// Complete binary tree in an array:
//
//           1 (index 0)
//          / \
//         2   3 (indices 1, 2)
//        / \ / \
//       4  5 6  7 (indices 3, 4, 5, 6)
//
// Array: [1, 2, 3, 4, 5, 6, 7]
//         0  1  2  3  4  5  6
 
// Given a node at index i:
function leftChildIndex(i: number): number {
    return 2 * i + 1;  // Left child is always at odd index
}
 
function rightChildIndex(i: number): number {
    return 2 * i + 2;  // Right child is always at even index (> 1)
}
 
function parentIndex(i: number): number {
    return Math.floor((i - 1) / 2);
}
 
// Examples:
// Node at index 0 (value 1):
//   Left child: 2*0+1 = 1 (value 2) ✓
//   Right child: 2*0+2 = 2 (value 3) ✓
 
// Node at index 1 (value 2):
//   Left child: 2*1+1 = 3 (value 4) ✓
//   Right child: 2*1+2 = 4 (value 5) ✓
//   Parent: (1-1)/2 = 0 (value 1) ✓
 
// The formulas DEPEND ON the left/right distinction:
// - Odd indices are always left children
// - Even indices (>1) are always right children

Symmetric binary trees (mirrors):

Two trees are mirrors of each other if swapping left and right throughout one produces the other:

     Original           Mirror
        A                  A
       / \                / \
      B   C              C   B
     /     \            /     \
    D       E          E       D

A tree is symmetric (self-similar) if it equals its own mirror:

     Symmetric Tree
          A
         / \
        B   B
       / \ / \
      C  D D  C

These concepts only make sense because left and right are distinct. The 'mirror' concept requires a distinction to reflect.

Symmetry as a Tree Property

Checking tree symmetry is a classic interview problem. The insight is comparing left and right recursively: a tree is symmetric if its left subtree is a mirror of its right subtree. This requires understanding that left/right are distinct and that 'mirror' means swapping them.

Writing Algorithms with Left/Right Awareness

When implementing binary tree algorithms, you'll constantly make decisions about how to handle left and right children. Here are key patterns:

Pattern 1: Treat left and right symmetrically

For many problems, left and right children receive identical treatment:

Counting nodes: count(left) + count(right) + 1
Finding max depth: max(depth(left), depth(right)) + 1
Summing values: sum(left) + sum(right) + current

Pattern 2: Handle left and right differently

Some problems require different handling:

BST operations: go left for smaller, right for larger
Certain path problems: track whether we're going left or right
Printing by level: typically process left before 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
// SYMMETRIC: Left and right treated identically
function maxDepth(node: TreeNode | null): number {
    if (!node) return 0;
    
    // Same logic for both children
    const leftDepth = maxDepth(node.left);
    const rightDepth = maxDepth(node.right);
    
    return Math.max(leftDepth, rightDepth) + 1;
}
 
// ASYMMETRIC: BST insertion treats left/right differently
function bstInsert(node: BSTNode | null, value: number): BSTNode {
    if (!node) return { value, left: null, right: null };
    
    if (value < node.value) {
        // Smaller values go LEFT - specific to left
        node.left = bstInsert(node.left, value);
    } else {
        // Larger values go RIGHT - specific to right
        node.right = bstInsert(node.right, value);
    }
    
    return node;
}
 
// ASYMMETRIC: Finding leftmost node
function leftmost(node: TreeNode | null): TreeNode | null {
    if (!node) return null;
    
    // Only traverse left - completely ignore right
    while (node.left) {
        node = node.left;
    }
    
    return node;
}
 
// ASYMMETRIC: Building right-skewed tree
function buildRightSkewed(values: number[]): TreeNode | null {
    if (values.length === 0) return null;
    
    const root: TreeNode = { value: values[0], left: null, right: null };
    let current = root;
    
    for (let i = 1; i < values.length; i++) {
        // Every node added as RIGHT child only
        current.right = { value: values[i], left: null, right: null };
        current = current.right;
    }
    
    return root;
}

Pattern 3: Combining results from left and right

Many problems combine subtree results:

function diameter(node: TreeNode | null): [number, number] {
    // Returns [diameter, height]
    if (!node) return [0, -1];
    
    const [leftDiam, leftHeight] = diameter(node.left);
    const [rightDiam, rightHeight] = diameter(node.right);
    
    // Diameter passing through this node
    const throughThis = leftHeight + rightHeight + 2;
    
    // Maximum of: left diameter, right diameter, or through this node
    const maxDiam = Math.max(leftDiam, rightDiam, throughThis);
    
    return [maxDiam, Math.max(leftHeight, rightHeight) + 1];
}

The key is understanding what information comes from each subtree and how to combine it.

Thinking in Subtrees

The mental model for binary tree algorithms is: 'What do I need from my left subtree? What do I need from my right subtree? How do I combine them with my current node?' The left/right distinction structures this thinking, even when both are treated symmetrically.

Edge Cases and Special Nodes

The left/right distinction creates special cases that algorithms must handle:

Nodes with only one child:

When a node has exactly one child, we must distinguish:

Left-only node: Has left child, no right child
Right-only node: Has right child, no left child

These are different configurations with different implications:

    Left-Only          Right-Only
        A                   A
       /                     \
      B                       B

In some algorithms (like BST deletion), we must identify which case applies.

Node Type Classification
Node Type	Left Child	Right Child	Detection	Common Name
Leaf	null	null	!left && !right	External node
Left-only	exists	null	left && !right	Single-child node
Right-only	null	exists	!left && right	Single-child node
Full node	exists	exists	left && right	Internal node

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
function classifyNode(node: TreeNode | null): string {
    if (!node) return 'empty';
    
    const hasLeft = node.left !== null;
    const hasRight = node.right !== null;
    
    if (!hasLeft && !hasRight) {
        return 'leaf';           // No children
    } else if (hasLeft && !hasRight) {
        return 'left-only';      // Only left child
    } else if (!hasLeft && hasRight) {
        return 'right-only';     // Only right child
    } else {
        return 'full';           // Both children
    }
}
 
// BST Deletion - must handle each case
function deleteNode(root: BSTNode | null, key: number): BSTNode | null {
    if (!root) return null;
    
    if (key < root.value) {
        root.left = deleteNode(root.left, key);
    } else if (key > root.value) {
        root.right = deleteNode(root.right, key);
    } else {
        // Found node to delete - handle by type
        if (!root.left && !root.right) {
            // LEAF: Just remove
            return null;
        } else if (!root.right) {
            // LEFT-ONLY: Replace with left child
            return root.left;
        } else if (!root.left) {
            // RIGHT-ONLY: Replace with right child
            return root.right;
        } else {
            // FULL: Find inorder successor (leftmost in right subtree)
            let successor = root.right;
            while (successor.left) {
                successor = successor.left;
            }
            root.value = successor.value;
            root.right = deleteNode(root.right, successor.value);
        }
    }
    
    return root;
}

Handle All Four Cases

Many binary tree bugs come from not handling all node types. When writing algorithms, explicitly consider: What if this node is a leaf? What if it has only a left child? What if it has only a right child? What if it has both? The left/right distinction doubles the single-child cases we must consider.

Summary: The Semantic Power of Left and Right

The distinction between left and right children is one of the most powerful aspects of binary trees. It transforms a simple hierarchical structure into a data structure that can encode ordering, support efficient search, and represent complex expressions.

Key Takeaways

•Left and right are semantically distinct — Swapping them creates a different tree, unlike general trees where child order is arbitrary
•BSTs encode ordering through left/right — 'Left = smaller, right = larger' enables O(log n) search
•Traversals depend on left-before-right convention — Preorder, inorder, and postorder assume this ordering
•Expression trees preserve operand order — Left/right matters critically for non-commutative operations like subtraction and division
•Array representation uses left/right for index calculation — Child positions at 2i+1 (left) and 2i+2 (right)
•Single-child nodes come in two flavors — Left-only and right-only require separate handling in algorithms
•Symmetry and mirroring require the distinction — These concepts only exist because left ≠ right

Looking ahead:

Now that we understand the conceptual foundations—what a binary tree is, why two children is optimal, and how left/right carry meaning—we're ready to make this concrete. The next page explores node-based representation in code: how to implement binary trees in actual programs, with all the practical details of memory allocation, pointer management, and common implementation patterns.

Distinction Mastered

You now understand that 'left' and 'right' aren't just positional labels—they're semantic carriers that enable binary search trees, proper expression evaluation, and meaningful tree algorithms. This distinction is the bridge between theory and practice.