Module 06: Trees — Traversals, BSTs, Self-Balancing & Subtree DP

Goal: Master tree anatomy, recursive and iterative traversals (DFS/BFS), Morris $O(1)$ space traversal, Binary Search Tree invariants and rotations, Lowest Common Ancestor (LCA), and Subtree DP patterns.
Language: C++ (C++17/C++20)
Prerequisites: Modules 01 to 05.

📑 Table of Contents

Under the Hood: Binary Tree Anatomy & Properties
Complete DFS & BFS Traversals (Recursive & Iterative)
Morris In-Order Traversal ($O(1)$ Auxiliary Space)
Binary Search Trees (BST): Search, Insert & 3-Case Deletion
Self-Balancing Trees: AVL Rotations & Red-Black Invariants
Core Tree Algorithmic Patterns
6 Practice Problems with Detailed Solutions
Top 10 FAANG Interview Questions

1. Under the Hood: Binary Tree Anatomy & Properties

A Binary Tree is a hierarchical non-linear data structure where each node has at most two children (left and right).

                    ┌─────────┐
                    │    1    │  <-- Root (Depth = 0, Level = 1)
                    └──┬───┬──┘
             ┌─────────┘   └─────────┐
             ▼                       ▼
        ┌─────────┐             ┌─────────┐
        │    2    │             │    3    │  <-- Internal Nodes (Depth = 1)
        └──┬───┬──┘             └──┬──────┘
     ┌─────┘   └─────┐             └─────┐
     ▼               ▼                   ▼
┌─────────┐     ┌─────────┐         ┌─────────┐
│    4    │     │    5    │         │    6    │  <-- Leaves (Depth = 2, Height = 0)
└─────────┘     └─────────┘         └─────────┘

1.1 Types of Binary Trees

Full Binary Tree: Every node has either 0 or 2 children.
Complete Binary Tree: All levels are completely filled except possibly the last, which is filled from left to right.
Perfect Binary Tree: All internal nodes have 2 children, and all leaves are at the exact same depth. Total nodes $N = 2^{h+1} - 1$.
Balanced Binary Tree: For every node, $| \text{height}(\text{left}) - \text{height}(\text{right}) | \le 1$. Height is guaranteed $O(\log N)$.
Degenerate (Skewed) Tree: Every internal node has only one child. Degrades to a linked list with $O(N)$ height.

1.2 C++ Node Definition

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

2. Complete DFS & BFS Traversals (Recursive & Iterative)

       [ 1 ]
      /     \
   [ 2 ]   [ 3 ]
   /   \
 [ 4 ] [ 5 ]

Pre-Order  (Root -> Left -> Right): 1, 2, 4, 5, 3
In-Order   (Left -> Root -> Right): 4, 2, 5, 1, 3  (Sorted order for BST!)
Post-Order (Left -> Right -> Root): 4, 5, 2, 3, 1
Level-Order (BFS by depth):         1, 2, 3, 4, 5

2.1 Iterative In-Order Traversal using Stack

#include <vector>
#include <stack>

std::vector<int> inorderTraversal(TreeNode* root) {
    std::vector<int> result;
    std::stack<TreeNode*> st;
    TreeNode* curr = root;
    
    while (curr != nullptr || !st.empty()) {
        // Reach leftmost node of current subtree
        while (curr != nullptr) {
            st.push(curr);
            curr = curr->left;
        }
        
        curr = st.top();
        st.pop();
        result.push_back(curr->val);
        
        // Move to right subtree
        curr = curr->right;
    }
    
    return result;
}

2.2 Breadth-First Search (Level-Order Traversal)

#include <vector>
#include <queue>

std::vector<std::vector<int>> levelOrder(TreeNode* root) {
    std::vector<std::vector<int>> result;
    if (!root) return result;
    
    std::queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        int levelSize = q.size();
        std::vector<int> currentLevel;
        currentLevel.reserve(levelSize);
        
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* node = q.front();
            q.pop();
            currentLevel.push_back(node->val);
            
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        result.push_back(std::move(currentLevel));
    }
    
    return result;
}

3. Morris In-Order Traversal ($O(1)$ Auxiliary Space)

Morris traversal creates temporary Threaded Links from the in-order predecessor back to the current node, allowing traversal without recursion or stack.

std::vector<int> morrisInorder(TreeNode* root) {
    std::vector<int> result;
    TreeNode* curr = root;
    
    while (curr != nullptr) {
        if (curr->left == nullptr) {
            result.push_back(curr->val);
            curr = curr->right;
        } else {
            // Find in-order predecessor (rightmost node in left subtree)
            TreeNode* prev = curr->left;
            while (prev->right != nullptr && prev->right != curr) {
                prev = prev->right;
            }
            
            if (prev->right == nullptr) {
                // Establish thread link
                prev->right = curr;
                curr = curr->left;
            } else {
                // Thread link already exists -> break it and visit root
                prev->right = nullptr;
                result.push_back(curr->val);
                curr = curr->right;
            }
        }
    }
    
    return result;
}
// Time Complexity: O(N) (each edge is traversed at most 3 times)
// Space Complexity: O(1) auxiliary!

4. Binary Search Trees (BST): Search, Insert & 3-Case Deletion

The BST Invariant

For every node $X$: $$\text{All nodes in } \text{LeftSubtree}(X) < X.\text{val} < \text{All nodes in } \text{RightSubtree}(X)$$

4.1 Deleting a Node from BST (3 Cases)

Case 1: Node is a Leaf (No Children): Simply delete the node and return nullptr.
Case 2: Node has One Child: Bypass the node by returning its non-null child.
Case 3: Node has Two Children: Find its In-Order Successor (smallest node in right subtree), copy successor value to current node, and recursively delete the successor from the right subtree.

TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) return nullptr;
    
    if (key < root->val) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    } else {
        // Node found!
        if (!root->left) {
            TreeNode* rightChild = root->right;
            delete root;
            return rightChild;
        } else if (!root->right) {
            TreeNode* leftChild = root->left;
            delete root;
            return leftChild;
        }
        
        // Two children: Find in-order successor
        TreeNode* successor = root->right;
        while (successor->left != nullptr) {
            successor = successor->left;
        }
        
        root->val = successor->val;
        root->right = deleteNode(root->right, successor->val);
    }
    return root;
}

5. Self-Balancing Trees: AVL Rotations & Red-Black Invariants

5.1 AVL Tree Rotations

When $\text{BalanceFactor} = \text{height}(\text{left}) - \text{height}(\text{right})$ becomes $\pm 2$:

Right Rotation (LL Case):             Left Rotation (RR Case):
        [ Z ]                                 [ X ]
       /                                           \
     [ Y ]         ===>       [ Y ]                 [ Y ]       ===>       [ Y ]
    /                        /     \                     \                /     \
  [ X ]                    [ X ]   [ Z ]                 [ Z ]          [ X ]   [ Z ]

Left-Right (LR): Left rotate left child, then Right rotate parent.
Right-Left (RL): Right rotate right child, then Left rotate parent.

6. Core Tree Algorithmic Patterns

6.1 Subtree Return Pattern (Bottom-Up Information Passing)

Child passes answers to parent; parent computes answer passing through root and updates a global/reference maximum.

6.2 Lowest Common Ancestor (LCA)

In BST: If $p$ and $q$ are both smaller than root, go left. If both larger, go right. Otherwise root is the split point (LCA).
In General Binary Tree: If left and right recursive searches both return non-null, root is the LCA.

7. 6 Practice Problems with Detailed Solutions

Problem 1: Binary Tree Maximum Path Sum (LeetCode #124 - Hard)

Problem: Return the maximum path sum of any non-empty path in a binary tree (path does not need to pass through root).

#include <algorithm>
#include <climits>

class SolutionMaxPathSum {
private:
    int globalMax = INT_MIN;

    int maxGain(TreeNode* node) {
        if (!node) return 0;
        
        // Max sum on left and right subtrees (ignore negative sums)
        int leftGain = std::max(maxGain(node->left), 0);
        int rightGain = std::max(maxGain(node->right), 0);
        
        // Price of the path passing through this node as highest point
        int currentPathPrice = node->val + leftGain + rightGain;
        globalMax = std::max(globalMax, currentPathPrice);
        
        // Return maximum gain this node can contribute to its parent
        return node->val + std::max(leftGain, rightGain);
    }

public:
    int maxPathSum(TreeNode* root) {
        globalMax = INT_MIN;
        maxGain(root);
        return globalMax;
    }
};
// Time Complexity: O(N)
// Space Complexity: O(H) where H is tree height

Problem 2: Lowest Common Ancestor of a Binary Tree (LeetCode #236 - Medium)

Problem: Given a binary tree, find the lowest common ancestor (LCA) of two given nodes p and q.

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    
    // If both left and right return non-null, p and q are in separate subtrees
    if (left && right) return root;
    
    return left ? left : right;
}
// Time Complexity: O(N)
// Space Complexity: O(H)

Problem 3: Serialize and Deserialize Binary Tree (LeetCode #297 - Hard)

Problem: Design an algorithm to serialize a binary tree into a string and deserialize that string back into the original tree.

#include <string>
#include <sstream>

class Codec {
private:
    void serializeHelper(TreeNode* root, std::ostringstream& out) {
        if (!root) {
            out << "# ";
            return;
        }
        out << root->val << " ";
        serializeHelper(root->left, out);
        serializeHelper(root->right, out);
    }

    TreeNode* deserializeHelper(std::istringstream& in) {
        std::string val;
        in >> val;
        if (val == "#" || val.empty()) {
            return nullptr;
        }
        TreeNode* node = new TreeNode(std::stoi(val));
        node->left = deserializeHelper(in);
        node->right = deserializeHelper(in);
        return node;
    }

public:
    std::string serialize(TreeNode* root) {
        std::ostringstream out;
        serializeHelper(root, out);
        return out.str();
    }

    TreeNode* deserialize(std::string data) {
        std::istringstream in(data);
        return deserializeHelper(in);
    }
};
// Time Complexity: O(N)
// Space Complexity: O(N)

Problem 4: Validate Binary Search Tree (LeetCode #98 - Medium)

Problem: Determine if a binary tree is a valid BST.

class SolutionValidateBST {
private:
    bool isValidHelper(TreeNode* node, long long low, long long high) {
        if (!node) return true;
        if (node->val <= low || node->val >= high) return false;
        
        return isValidHelper(node->left, low, node->val) &&
               isValidHelper(node->right, node->val, high);
    }

public:
    bool isValidBST(TreeNode* root) {
        return isValidHelper(root, LLONG_MIN, LLONG_MAX);
    }
};
// Time Complexity: O(N)
// Space Complexity: O(H)

Problem 5: Construct Binary Tree from Preorder & Inorder (LeetCode #105 - Medium)

Problem: Given preorder and inorder traversal arrays, construct and return the binary tree.

#include <vector>
#include <unordered_map>

class SolutionBuildTree {
private:
    std::unordered_map<int, int> inMap;
    int preIndex = 0;

    TreeNode* build(const std::vector<int>& preorder, int inStart, int inEnd) {
        if (inStart > inEnd) return nullptr;
        
        int rootVal = preorder[preIndex++];
        TreeNode* root = new TreeNode(rootVal);
        int inIndex = inMap[rootVal];
        
        root->left = build(preorder, inStart, inIndex - 1);
        root->right = build(preorder, inIndex + 1, inEnd);
        return root;
    }

public:
    TreeNode* buildTree(std::vector<int>& preorder, std::vector<int>& inorder) {
        inMap.clear();
        preIndex = 0;
        for (int i = 0; i < inorder.size(); ++i) inMap[inorder[i]] = i;
        return build(preorder, 0, inorder.size() - 1);
    }
};
// Time Complexity: O(N)
// Space Complexity: O(N) for hash map

Problem 6: Diameter of Binary Tree (LeetCode #543 - Easy/Medium)

Problem: Return the length of the longest path between any two nodes in a tree.

class SolutionDiameter {
private:
    int maxDiameter = 0;

    int depth(TreeNode* node) {
        if (!node) return 0;
        int leftDepth = depth(node->left);
        int rightDepth = depth(node->right);
        
        maxDiameter = std::max(maxDiameter, leftDepth + rightDepth);
        return 1 + std::max(leftDepth, rightDepth);
    }

public:
    int diameterOfBinaryTree(TreeNode* root) {
        maxDiameter = 0;
        depth(root);
        return maxDiameter;
    }
};
// Time Complexity: O(N)
// Space Complexity: O(H)

8. Top 10 FAANG Interview Questions

Q1: Why does In-Order traversal of a BST produce keys in strictly ascending order?

Answer: The BST invariant specifies that for any node $X$, all keys in its left subtree are $< X$, and all keys in its right subtree are $> X$. In-order traversal visits $\text{Left} \to \text{Root} \to \text{Right}$. By induction, the entire left subtree is processed (smallest values), then the root, then the entire right subtree (largest values).

Q2: Can you reconstruct a unique Binary Tree given only Pre-Order and Post-Order traversals?

Answer: No, not in general. If any node has only one child, we cannot determine whether that child belongs in the left or right subtree. Exception: If the binary tree is known to be a Full Binary Tree (every node has 0 or 2 children), unique reconstruction is possible.

Q3: What is the maximum number of nodes in a Binary Tree of height $H$?

Answer: A perfect binary tree of height $H$ (where root is height 0) has $2^{H+1} - 1$ nodes. At level $i$, there are $2^i$ nodes. $$\sum_{i=0}^H 2^i = 2^{H+1} - 1$$

Q4: What is the difference between AVL Trees and Red-Black Trees?

Answer:

AVL Trees: Strictly balanced ($|h_L - h_R| \le 1$). Height is at most $1.44 \log_2 N$. Faster lookups due to shallower height, but inserts/deletes require more rotations.
Red-Black Trees: Loosely balanced (longest path is at most $2 \times$ shortest path). Height at most $2 \log_2 N$. Faster insertions and deletions (at most 2 rotations for insert, 3 for delete). Used in C++ STL std::map and std::set.

Q5: How do you find the In-Order Successor of a node in a BST if parent pointers are available?

Answer:

If the node has a right subtree: Successor is the leftmost node in the right subtree.
If no right subtree: Walk up parent pointers until the current node is the left child of its parent. That parent is the in-order successor.

Q6: What is a Threaded Binary Tree?

Answer: A binary tree where null left child pointers point to the in-order predecessor, and null right child pointers point to the in-order successor. This eliminates the need for recursion or call stacks during traversals.

Q7: How do you check if two binary trees are isomorphic / symmetric?

Answer: Two trees $T_1$ and $T_2$ are symmetric if:

Both are null (true), or one is null (false).
$T_1.\text{val} == T_2.\text{val}$.
$T_1.\text{left}$ is symmetric with $T_2.\text{right}$, AND $T_1.\text{right}$ is symmetric with $T_2.\text{left}$.

Q8: What is the maximum recursion depth for a binary tree traversal?

Answer: The maximum recursion depth equals the height of the tree $H$. In the best case (balanced tree), $H = O(\log N)$. In the worst case (skewed tree), $H = O(N)$, which can cause a stack overflow for large $N \ge 10^5$.

Q9: How can you implement a BST iterator with $O(1)$ average `next()` and $O(H)$ space?

Answer: Push all left nodes of the root onto a stack. For next():

Pop top node $X$ (which is the current smallest).
If $X$ has a right child, push that right child and all of its consecutive left descendants onto the stack.
Return $X.\text{val}$. Amortized time is $O(1)$ because each node is pushed and popped at most once.

Q10: How do you find the boundary traversal of a Binary Tree?

Answer:

Print root.
Print left boundary (top-down, excluding leaves).
Print all leaf nodes (left-to-right using DFS).
Print right boundary (bottom-up, excluding leaves). Time: $O(N)$, Space: $O(H)$.

06-trees.md

Module 06: Trees — Traversals, BSTs, Self-Balancing & Subtree DP

📑 Table of Contents

1. Under the Hood: Binary Tree Anatomy & Properties

1.1 Types of Binary Trees

1.2 C++ Node Definition

2. Complete DFS & BFS Traversals (Recursive & Iterative)

2.1 Iterative In-Order Traversal using Stack

2.2 Breadth-First Search (Level-Order Traversal)

3. Morris In-Order Traversal ($O(1)$ Auxiliary Space)

4. Binary Search Trees (BST): Search, Insert & 3-Case Deletion

The BST Invariant

4.1 Deleting a Node from BST (3 Cases)

5. Self-Balancing Trees: AVL Rotations & Red-Black Invariants

5.1 AVL Tree Rotations

6. Core Tree Algorithmic Patterns

6.1 Subtree Return Pattern (Bottom-Up Information Passing)

6.2 Lowest Common Ancestor (LCA)

7. 6 Practice Problems with Detailed Solutions

Problem 1: Binary Tree Maximum Path Sum (LeetCode #124 - Hard)

Problem 2: Lowest Common Ancestor of a Binary Tree (LeetCode #236 - Medium)

Problem 3: Serialize and Deserialize Binary Tree (LeetCode #297 - Hard)

Problem 4: Validate Binary Search Tree (LeetCode #98 - Medium)

Problem 5: Construct Binary Tree from Preorder & Inorder (LeetCode #105 - Medium)

Problem 6: Diameter of Binary Tree (LeetCode #543 - Easy/Medium)

8. Top 10 FAANG Interview Questions

Q1: Why does In-Order traversal of a BST produce keys in strictly ascending order?

Q2: Can you reconstruct a unique Binary Tree given only Pre-Order and Post-Order traversals?

Q3: What is the maximum number of nodes in a Binary Tree of height $H$?

Q4: What is the difference between AVL Trees and Red-Black Trees?

Q5: How do you find the In-Order Successor of a node in a BST if parent pointers are available?

Q6: What is a Threaded Binary Tree?

Q7: How do you check if two binary trees are isomorphic / symmetric?

Q8: What is the maximum recursion depth for a binary tree traversal?

Q9: How can you implement a BST iterator with $O(1)$ average next() and $O(H)$ space?

Q10: How do you find the boundary traversal of a Binary Tree?

Q9: How can you implement a BST iterator with $O(1)$ average `next()` and $O(H)$ space?