Tree Fundamentals

TL;DR

Trees organize data hierarchically with root at top and leaves at bottom. Traversals visit nodes in specific orders: preorder (root first) for copying, inorder (sorted for BSTs), postorder (root last) for cleanup, and level-order (BFS) for layered problems. Height measures longest path from node to leaf; depth measures distance from root. Recursive traversal naturally expresses tree algorithms through divide-and-conquer: recurse on subtrees, combine results at current node.

Core Concepts

Tree Terminology and Properties

Root is unique top node with no parent. Leaves are nodes without children. Internal nodes have at least one child.

Height of node is longest path to leaf below it. Leaf height = 0; single-node tree height = 0; empty tree height = -1 (convention varies).

Depth of node is distance from root. Root depth = 0; children depth = 1, etc.

Tree height is root's height, representing overall tree's vertical span.

Balanced tree has height O(log n), meaning all paths root-to-leaf are similar length. Unbalanced trees degrade to linked lists in worst case.

Tree Traversals

Preorder (root, left, right) visits root before subtrees. Natural for tree copying: create node, then recurse left, then right. Mirrors tree structure.

Inorder (left, root, right) visits root between subtrees. For BSTs yields sorted order—fundamental property enabling searching.

Postorder (left, right, root) visits root after subtrees. Natural for deletion: delete children first, then node. Used in expression evaluation (postfix).

Level-order (BFS) visits all nodes at level k before level k+1. Uses queue. Reveals tree's depth structure; crucial for problems asking "levels."

Height and Depth Calculations

Height recursively: for each node, height = max(left.height, right.height) + 1. Base case: null has height -1.

Depth iteratively: BFS from root, tracking distance; or recursively: depth = parent.depth + 1.

Balanced check: tree is balanced if all nodes satisfy |left.height - right.height| ≤ 1. Can check during height calculation for O(n) single pass.

Tree Construction and Serialization

From sorted array: always pick middle as root, recursively construct left/right subtrees. Creates balanced tree.

Serialization converts tree to string/array. Preorder with nulls: "1,2,null,null,3" represents tree. Deserialize by parsing array, recursively build.

Space efficiency matters: represent only meaningful information; nulls at end unnecessary if order known.

Key Algorithms and Techniques

Recursive Traversal Template

Visit node, then recurse left and right in varying orders.

Height Calculation Single Pass

During traversal, compute height incrementally; track heights in dictionary.

Level-Order with Queue

Enqueue level-size and track current level, separating levels naturally.

Balanced Tree Validation

During height calculation, check balance condition at each node.

Practical Example

Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Preorder traversal
def preorder(root):
    result = []
    def dfs(node):
        if not node:
            return
        result.append(node.val)
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return result

# Inorder traversal
def inorder(root):
    result = []
    def dfs(node):
        if not node:
            return
        dfs(node.left)
        result.append(node.val)
        dfs(node.right)
    dfs(root)
    return result

# Postorder traversal
def postorder(root):
    result = []
    def dfs(node):
        if not node:
            return
        dfs(node.left)
        dfs(node.right)
        result.append(node.val)
    dfs(root)
    return result

# Level-order traversal
def levelOrder(root):
    if not root:
        return []
    from collections import deque
    queue = deque([root])
    result = []
    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

# Height of tree
def height(root):
    if not root:
        return -1
    return max(height(root.left), height(root.right)) + 1

# Check if balanced
def isBalanced(root):
    def dfs(node):
        if not node:
            return True, -1
        left_balanced, left_height = dfs(node.left)
        right_balanced, right_height = dfs(node.right)
        balanced = left_balanced and right_balanced and abs(left_height - right_height) <= 1
        return balanced, max(left_height, right_height) + 1
    return dfs(root)[0]

# Test
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(f"Preorder: {preorder(root)}")
print(f"Inorder: {inorder(root)}")
print(f"Level-order: {levelOrder(root)}")
print(f"Height: {height(root)}")
print(f"Balanced: {isBalanced(root)}")

Java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

class TreeTraversals {
    static List<Integer> preorder(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root, result, "pre");
        return result;
    }

    static List<Integer> inorder(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root, result, "in");
        return result;
    }

    static void dfs(TreeNode node, List<Integer> result, String order) {
        if (node == null) return;
        if ("pre".equals(order)) result.add(node.val);
        dfs(node.left, result, order);
        if ("in".equals(order)) result.add(node.val);
        dfs(node.right, result, order);
        if ("post".equals(order)) result.add(node.val);
    }

    static int height(TreeNode root) {
        if (root == null) return -1;
        return Math.max(height(root.left), height(root.right)) + 1;
    }

    static boolean isBalanced(TreeNode root) {
        return helper(root)[0];
    }

    static Object[] helper(TreeNode node) {
        if (node == null) return new Object[]{true, -1};
        Object[] left = helper(node.left);
        Object[] right = helper(node.right);
        boolean balanced = (boolean) left[0] && (boolean) right[0]
            && Math.abs((int) left[1] - (int) right[1]) <= 1;
        int height = Math.max((int) left[1], (int) right[1]) + 1;
        return new Object[]{balanced, height};
    }
}

TypeScript

class TreeNode {
    val: number;
    left: TreeNode | null = null;
    right: TreeNode | null = null;
    constructor(val: number) { this.val = val; }
}

function preorder(root: TreeNode | null): number[] {
    const result: number[] = [];
    function dfs(node: TreeNode | null) {
        if (!node) return;
        result.push(node.val);
        dfs(node.left);
        dfs(node.right);
    }
    dfs(root);
    return result;
}

function levelOrder(root: TreeNode | null): number[][] {
    if (!root) return [];
    const result: number[][] = [];
    const queue: TreeNode[] = [root];
    while (queue.length > 0) {
        const levelSize = queue.length;
        const level: number[] = [];
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!;
            level.push(node.val);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        result.push(level);
    }
    return result;
}

function height(root: TreeNode | null): number {
    if (!root) return -1;
    return Math.max(height(root.left), height(root.right)) + 1;
}

Tree Construction from Arrays and Serialization

Building Balanced BST from Sorted Array

def build_bst_from_array(arr):
    """Create balanced BST from sorted array"""
    if not arr:
        return None
    mid = len(arr) // 2
    root = TreeNode(arr[mid])
    root.left = build_bst_from_array(arr[:mid])
    root.right = build_bst_from_array(arr[mid + 1:])
    return root

# Example: [1, 2, 3, 4, 5, 6, 7]
# Becomes:
#        4
#       / \
#      2   6
#     / \ / \
#    1  3 5  7

Tree Serialization and Deserialization

def serialize_tree(root):
    """Convert tree to string representation"""
    if not root:
        return "null"
    return f"{root.val},{serialize_tree(root.left)},{serialize_tree(root.right)}"

def deserialize_tree(data):
    """Reconstruct tree from string representation"""
    nodes = data.split(',')
    index = 0

    def build():
        nonlocal index
        if nodes[index] == "null":
            index += 1
            return None
        root = TreeNode(int(nodes[index]))
        index += 1
        root.left = build()
        root.right = build()
        return root

    return build()

# Example
tree = TreeNode(1, TreeNode(2), TreeNode(3))
serialized = serialize_tree(tree)  # "1,2,null,null,3,null,null"
restored = deserialize_tree(serialized)  # Reconstructed tree

Advanced Traversal Techniques

Morris Traversal (Space-Optimized Inorder)

Traditional inorder traversal uses O(h) stack space. Morris traversal achieves O(1) space using tree threading:

def morris_inorder(root):
    result = []
    current = root

    while current:
        if not current.left:
            result.append(current.val)
            current = current.right
        else:
            # Find rightmost node in left subtree
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right

            if not predecessor.right:
                # First time visiting: thread the tree
                predecessor.right = current
                current = current.left
            else:
                # Second time visiting: restore and process
                result.append(current.val)
                predecessor.right = None
                current = current.right

    return result

Iterative Traversal with Stack

def iterative_preorder(root):
    if not root:
        return []
    result = []
    stack = [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

def iterative_inorder(root):
    result = []
    stack = []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
    return result

def iterative_postorder(root):
    # More complex: two-stack approach or reverse preorder
    if not root:
        return []
    stack1 = [root]
    stack2 = []
    while stack1:
        node = stack1.pop()
        stack2.append(node)
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    return [node.val for node in reversed(stack2)]

Vertical/Diagonal Traversals

def vertical_order(root):
    if not root:
        return []
    from collections import defaultdict, deque
    col_map = defaultdict(list)
    queue = deque([(root, 0)])  # (node, column)

    while queue:
        node, col = queue.popleft()
        col_map[col].append(node.val)
        if node.left:
            queue.append((node.left, col - 1))
        if node.right:
            queue.append((node.right, col + 1))

    return [col_map[col] for col in sorted(col_map)]

Common Pitfalls and Solutions

warning

Confusing traversal orders: Memorize: Preorder = root first (NLR), Inorder = root middle (LNR), Postorder = root last (LRN). Mnemonic: alphabetical order N, L, R indicates when to visit Node relative to Left/Right subtrees.

Height base case confusion: Null node height is -1 (not 0), so single node = 0. Different conventions exist; be consistent. When in doubt, verify with examples (what's height of node with one child?).

Depth vs Height mixing: Depth measures distance from root (top-down); height measures distance to leaf (bottom-up). Depth increases as you go down; height decreases.

Level-order implementation: Queue must separate levels explicitly using level-size counter; simple queue traversal processes nodes but loses level information.

Not handling null checks: Null nodes appear frequently in sparse trees. Every recursive call needs null check or crashes. Test with single-node and empty trees.

Off-by-one in height: Height of empty tree is -1 (convention); height of single node is 0; height of tree with two levels is 1.

Complexity Analysis

Operation	Time	Space	Notes
Inorder traversal	O(n)	O(h)	h = height, O(n) worst case (unbalanced)
Preorder traversal	O(n)	O(h)	Same as inorder
Postorder traversal	O(n)	O(h)	Same as inorder
Level-order (BFS)	O(n)	O(w)	w = max width (can be O(n) for unbalanced)
Height calculation	O(n)	O(h)	Must visit all nodes
Balance check	O(n)	O(h)	Optimal: O(n) single pass during height
Morris traversal	O(n)	O(1)	No explicit stack; more complex code

Real-World Applications

Expression Trees: Parse and evaluate math expressions. Inorder gives infix notation; postorder evaluates.

Document Object Model (DOM): HTML/XML structure is a tree. Traversal finds specific elements.

File Systems: Directories form a tree. DFS (preorder) for file listing; postorder for cleanup (delete children before parent).

Decision Trees: Machine learning models. Traversal for prediction (left = condition false, right = true).

Binary Search Trees: Inorder traversal gives sorted order (critical for validation).

Heap Operations: Specialized tree operations; but understanding tree traversal helps implement heapify.

Self-Check

1. Trace and verify: Draw a 3-node tree, trace preorder, inorder, postorder. Verify each matches its definition.
2. Height reasoning: Calculate height recursively. Why is null height -1? What if it was 0?
3. Traversal choice: For each scenario, which traversal? (a) Copy a tree, (b) Find max value, (c) Evaluate expression, (d) Print by level
4. Code practice: Implement all four traversals recursively and iteratively. Which is clearer?
5. Edge cases: What happens with empty tree? Single node? Skewed tree (linked list)?

Answers: (1) Practice by hand. (2) Null=-1 ensures single node has height 0. (3) a=preorder (mirror structure), b=any (compare), c=postorder (operands before operators), d=level-order. (4) Recursive is concise; iterative helps understand explicit stack.

One Takeaway

info

Tree traversals are fundamental building blocks for almost all tree algorithms. Inorder gives sorted BST order. Postorder naturally handles cleanup/deletion. Preorder mirrors structure. Level-order reveals depth structure. Master these traversals and most tree problems become straightforward recursive implementations.

References

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• McDowell, G. L. (2015). Cracking the Coding Interview (6th ed.). CareerCup.