Master DSA: Trees — Types, Traversals (Inorder, Preorder, Postorder) & Core Patterns

This chapter introduces the Tree data structure, moving from linear data structures (like Arrays, Linked Lists, Stacks, and Queues) to hierarchical, non-linear structures. We will explore core tree terminologies, mathematical properties, structural taxonomies, depth-first traversals (Inorder, Preorder, Postorder), and solve foundational coding interview problems using recursion.

1. Why Do We Need Trees? (The Paradigm Shift)

In linear data structures, elements are arranged sequentially, and each element has a unique predecessor and successor (except for the first and last elements). While linear structures are excellent for simple storage, they fail to represent hierarchical relationships efficiently.

Real-World Analogy

Consider a corporate organizational chart, a family genealogy tree, or the file directory system on your computer:

• A folder contains subfolders, which in turn contain files.
• A CEO has multiple Vice Presidents, who manage Directors, who manage individual contributors.

These relationships cannot be naturally modeled using a flat array or a singly linked list without sacrificing search, insertion, or structural clarity. Trees solve this by introducing a non-linear, hierarchical structure composed of nodes connected by directed edges.

2. Core Mental Model & Basic Terminologies

A Tree is a collection of nodes connected by directed edges, containing no cycles.

          Root Node (10)
             /      \
            /        \
     Left Child (5)  Right Child (15)

To master tree-based algorithms, you must first internalize these essential terminologies:

• Node: A structural container holding a data value and references (pointers) to its child nodes.
• Root: The topmost node of a tree. It has no parent. Every non-empty tree must have exactly one root node.
• Child: A node directly connected to another node when moving away from the root.
• Parent: A node that has direct references to one or more child nodes.
• Leaf Node: A node that has no children (its child references point to null).
• Siblings: Nodes that share the same parent node.
• Subtree: Any node within a tree, combined with all of its descendants, forms a subtree.
• Levels: The generation steps starting from the root. The root is at Level 1 (or Level 0, depending on convention), its children are at Level 2, and so on.

Depth vs. Height

• Depth: The distance from the root node to the target node. It is measured by counting the number of edges along the path.
• Height: The distance from the target node to the deepest leaf node along the longest path. The height of the root node is considered the height of the entire tree.

3. Mathematical Properties: Nodes vs. Edges

An edge is the link or connection between two nodes. There is a strict mathematical relationship between the number of nodes ($N$) and the number of edges ($E$) in any valid tree:

Why does this relationship hold?

Every node in a tree, except for the root node, has exactly one incoming edge from its parent. Since the root node has no parent, it has no incoming edge. Therefore, the total number of edges must be exactly one less than the total number of nodes.

4. Taxonomy of Trees (Types of Trees)

Trees are categorized based on their structural constraints, ordering rules, and balancing properties.

Red-Black Tree Balancing Rules

To guarantee $O(\log N)$ operations, a Red-Black Tree enforces these strict color properties:

1. Every node is colored either Red or Black.
2. The Root node is always Black.
3. No two adjacent Red nodes are allowed (a Red node cannot have a Red child).
4. Every path from a node to any of its descendant null nodes must contain the exact same number of Black nodes.

5. Tree Traversals: DFS vs. BFS Mental Models

To process or search data within a tree, we must visit every node systematically. There are two primary paradigms for tree traversal:

1. Depth-First Search (DFS)

DFS prioritizes going as deep as possible down a single branch before backtracking and moving to sibling branches. DFS is naturally implemented using recursion (which utilizes the call stack) or an explicit Stack.

• Inorder Traversal
• Preorder Traversal
• Postorder Traversal

2. Breadth-First Search (BFS)

BFS processes nodes level-by-level, visiting all nodes at the current depth before moving to the next level. BFS is typically implemented iteratively using a Queue.

6. Deep-Dive: Inorder Traversal (Left -> Root -> Right)

In an Inorder traversal, we traverse the left subtree first, visit the root node, and then traverse the right subtree.

Code Implementation (Java)

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

public class TreeTraversal {
    public void inorder(TreeNode root) {
        // Base Case
        if (root == null) {
            return;
        }
        
        inorder(root.left);             // 1. Traverse Left Subtree
        System.out.print(root.val + " "); // 2. Visit Root Node
        inorder(root.right);            // 3. Traverse Right Subtree
    }
}

Crucial Property: Performing an Inorder traversal on a Binary Search Tree (BST) always visits the nodes in sorted, ascending order.

7. Deep-Dive: Preorder Traversal (Root -> Left -> Right)

In a Preorder traversal, we visit the root node first, then traverse the left subtree, and finally traverse the right subtree. This is highly useful for creating a copy of a tree or serializing its structure.

Code Implementation (Java)

public class TreeTraversal {
    public void preorder(TreeNode root) {
        // Base Case
        if (root == null) {
            return;
        }
        
        System.out.print(root.val + " "); // 1. Visit Root Node
        preorder(root.left);            // 2. Traverse Left Subtree
        preorder(root.right);           // 3. Traverse Right Subtree
    }
}

8. Deep-Dive: Postorder Traversal (Left -> Right -> Root)

In a Postorder traversal, we traverse the left subtree first, then the right subtree, and finally visit the root node. This is ideal for deletion operations (deleting children before deleting the parent) and bottom-up calculations (like finding the height of a tree).

Code Implementation (Java)

public class TreeTraversal {
    public void postorder(TreeNode root) {
        // Base Case
        if (root == null) {
            return;
        }
        
        postorder(root.left);           // 1. Traverse Left Subtree
        postorder(root.right);          // 2. Traverse Right Subtree
        System.out.print(root.val + " "); // 3. Visit Root Node
    }
}

9. Step-by-Step Recursion Stack Walkthrough

Let us trace how the recursion stack behaves during an Inorder Traversal of the following binary tree:

        4
       / \
      3   5
     / \
    1   2

Execution Flow & Stack Trace

Traversal Outputs Comparison

Using the same sample tree, let's compare the final outputs of the three DFS strategies:

• Inorder (Left, Root, Right): 1 -> 3 -> 2 -> 4 -> 5
• Preorder (Root, Left, Right): 4 -> 3 -> 1 -> 2 -> 5
• Postorder (Left, Right, Root): 1 -> 2 -> 3 -> 5 -> 4

10. Coding Problem 1: Maximum Depth of a Binary Tree

Problem Statement

Given the root of a binary tree, return its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

        3
       / \
      9  20
        /  \
       15   7

Output: 3 (Path: 3 -> 20 -> 15 or 3 -> 20 -> 7)

Intuition & Bottom-Up Strategy

To find the maximum depth of a tree at any node, we can calculate the maximum depth of its left subtree and its right subtree, take the maximum of those two values, and add $1$ to account for the current node itself.

Code Implementation (Java)

public class Solution {
    public int maxDepth(TreeNode root) {
        // Base Case: An empty tree has a depth of 0
        if (root == null) {
            return 0;
        }
        
        // Recursive Relations
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        
        // Return the maximum of left and right subtrees + 1 (for current node)
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$, where $N$ is the total number of nodes in the tree. We must visit every node exactly once.
• Space Complexity: $\mathcal{O}(H)$, where $H$ is the height of the tree. This space is consumed by the recursive call stack. In the worst case (a completely skewed tree), $H = N$. In the best case (a balanced tree), $H = \log N$.

11. Coding Problem 2: Same Tree (Structural & Value Equality)

Problem Statement

Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical and the nodes have the exact same values.

Base Case Identification

When comparing two nodes p and q, there are four possible scenarios:

1. Both p and q are null $\rightarrow$ They are identical (Return true).
2. p is null and q is not null $\rightarrow$ They are not identical (Return false).
3. p is not null and q is null $\rightarrow$ They are not identical (Return false).
4. Both are not null, but their values differ (p.val != q.val) $\rightarrow$ They are not identical (Return false).

If none of these mismatch conditions are met, we recursively check if the left subtrees are identical and the right subtrees are identical.

Code Implementation (Java)

public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // Base Case 1: Both are null
        if (p == null && q == null) {
            return true;
        }
        
        // Base Case 2: One is null, the other is not
        if (p == null || q == null) {
            return false;
        }
        
        // Base Case 3: Values do not match
        if (p.val != q.val) {
            return false;
        }
        
        // Recursive Step: Both left and right subtrees must be identical
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(\min(N, M))$, where $N$ and $M$ are the number of nodes in trees p and q. We traverse up to the size of the smaller tree.
• Space Complexity: $\mathcal{O}(\min(H_1, H_2))$, representing the recursion stack depth, where $H_1$ and $H_2$ are the heights of the two trees.

12. Homework Challenge: Symmetric Trees (Mirror Image Check)

Problem Statement

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

        1
       / \
      2   2
     / \ / \
    3  4 4  3

Output: true

Conceptual Strategy & Hint

A tree is symmetric if its left subtree is a mirror image of its right subtree. To solve this, you can write a helper function isMirror(TreeNode t1, TreeNode t2) that compares two subtrees.

Instead of comparing left-to-left and right-to-right (as we did in isSameTree), you must compare:

• t1.left with t2.right
• t1.right with t2.left

Compare Left Subtree (t1)               Compare Right Subtree (t2)
         2                                       2
        / \                                     / \
  t1.left  t1.right                       t2.left  t2.right

Action Item: Implement this logic by modifying the isSameTree base cases and cross-comparing the left and right children.

13. Summary and Key Takeaways

• Trees are Hierarchical: They represent non-linear relationships, making them ideal for representing file systems, DOM structures, and sorted datasets.
• The Edge-Node Rule: Any valid tree with $N$ nodes always contains exactly $N - 1$ edges.
• Inorder Traversal (L-Root-R): Yields sorted values when executed on a Binary Search Tree (BST).
• Preorder Traversal (Root-L-R): Excellent for copying, cloning, or serializing a tree structure.
• Postorder Traversal (L-R-Root): Ideal for bottom-up calculations (like finding height/depth) and node deletion.
• Base Cases are Crucial: Tree recursion heavily relies on identifying correct base cases (e.g., handling null nodes) to prevent stack overflow errors.
• DFS Complexity: DFS traversals run in $\mathcal{O}(N)$ time and require $\mathcal{O}(H)$ auxiliary space due to the implicit recursion stack.