Complete DSA Series Part 9: Trees

FAANG Interview Prep

Your 12-step learning path • Currently on Step 9

Trees

Binary trees, traversals, expression trees, threaded trees

You Are Here

BST & Balanced Trees

Search, insert, delete, AVL, red-black, B-trees

Heaps, Sorting & Hashing

Min/max heaps, heapsort, hash tables, collision handling

Graphs, DP, Greedy & Backtracking

BFS, DFS, shortest paths, dynamic programming, optimization

Introduction to Trees

A tree is a hierarchical data structure consisting of nodes connected by edges. Unlike linear structures (arrays, linked lists), trees represent hierarchical relationships with a single root node and zero or more child nodes forming subtrees. Trees are fundamental in computer science, used in file systems, databases, compilers, and many algorithms.

Tree data structure showing root, internal nodes, and leaf nodes with labeled edges — Anatomy of a tree: root node at top, internal nodes with children, and leaf nodes at the bottom level

                            
                            Key Insight: Trees are recursive structures - every subtree is itself a tree. This recursive nature makes them perfect for divide-and-conquer algorithms. A binary tree with n nodes has n-1 edges and can have up to 2^h - 1 nodes at height h.
                        

Tree Terminology

                            Key Terms
                            
                                        Term
                                        Definition
                                    
                                        Root
                                        Topmost node with no parent
                                    
                                        Leaf
                                        Node with no children
                                    
                                        Internal Node
                                        Node with at least one child
                                    
                                        Height
                                        Longest path from node to leaf
                                    
                                        Depth
                                        Path length from root to node
                                    
                                        Level
                                        Depth + 1 (root is level 1)
                                    
                                        Degree
                                        Number of children of a node
                                    
                                        Ancestor/Descendant
                                        Nodes in the path from root

Term	Definition
Root	Topmost node with no parent
Leaf	Node with no children
Internal Node	Node with at least one child
Height	Longest path from node to leaf
Depth	Path length from root to node
Level	Depth + 1 (root is level 1)
Degree	Number of children of a node
Ancestor/Descendant	Nodes in the path from root

Types of Binary Trees

                            Binary Tree Types
                            Full Binary Tree: Every node has 0 or 2 children
Complete Binary Tree: All levels filled except possibly the last, filled left to right
Perfect Binary Tree: All internal nodes have 2 children, all leaves at same level
Balanced Binary Tree: Height of left and right subtrees differ by at most 1
Degenerate/Skewed: Each node has only one child (like a linked list)

                        

Tree Representation

Binary tree node structure with val, left pointer, and right pointer — Linked representation of a binary tree: each node stores a value and pointers to left and right children

# Binary Tree Node Class
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    
    def __repr__(self):
        return f"TreeNode({self.val})"

# Build a simple tree
#       1
#      / \
#     2   3
#    / \   \
#   4   5   6

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)

print(f"Root: {root.val}")
print(f"Left child: {root.left.val}")
print(f"Right child: {root.right.val}")

// Binary Tree Node Class
#include <iostream>

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

int main() {
    // Build a simple tree
    //       1
    //      / \
    //     2   3
    //    / \   \
    //   4   5   6
    
    TreeNode* 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);
    root->right->right = new TreeNode(6);
    
    std::cout << "Root: " << root->val << std::endl;
    std::cout << "Left child: " << root->left->val << std::endl;
    std::cout << "Right child: " << root->right->val << std::endl;
    
    return 0;
}

// Binary Tree Node Class

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int val) {
        this.val = val;
    }
    
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
    
    @Override
    public String toString() {
        return "TreeNode(" + val + ")";
    }
}

public class TreeDemo {
    public static void main(String[] args) {
        // Build a simple tree
        //       1
        //      / \
        //     2   3
        //    / \   \
        //   4   5   6
        
        TreeNode 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);
        root.right.right = new TreeNode(6);
        
        System.out.println("Root: " + root.val);
        System.out.println("Left child: " + root.left.val);
        System.out.println("Right child: " + root.right.val);
    }
}

# Array Representation (for Complete Binary Trees)
# Parent at index i: children at 2i+1 and 2i+2
# Child at index i: parent at (i-1)//2

class ArrayBinaryTree:
    def __init__(self, capacity=100):
        self.tree = [None] * capacity
        self.size = 0
    
    def insert(self, val):
        """Insert into complete binary tree"""
        if self.size >= len(self.tree):
            raise OverflowError("Tree is full")
        self.tree[self.size] = val
        self.size += 1
    
    def get_parent(self, i):
        """Get parent index"""
        if i == 0:
            return None
        return (i - 1) // 2
    
    def get_left_child(self, i):
        """Get left child index"""
        left = 2 * i + 1
        return left if left < self.size else None
    
    def get_right_child(self, i):
        """Get right child index"""
        right = 2 * i + 2
        return right if right < self.size else None
    
    def display(self):
        print("Array representation:", self.tree[:self.size])

# Build complete binary tree
arr_tree = ArrayBinaryTree()
for val in [1, 2, 3, 4, 5, 6, 7]:
    arr_tree.insert(val)

arr_tree.display()  # [1, 2, 3, 4, 5, 6, 7]
print(f"Parent of index 3: {arr_tree.get_parent(3)}")  # 1
print(f"Left child of index 1: {arr_tree.get_left_child(1)}")  # 3

// Array Representation (for Complete Binary Trees)
// Parent at index i: children at 2i+1 and 2i+2
// Child at index i: parent at (i-1)/2
#include <iostream>
#include <vector>
#include <optional>

template <typename T>
class ArrayBinaryTree {
private:
    std::vector<std::optional<T>> tree;
    size_t _size;

public:
    ArrayBinaryTree(int capacity = 100) : tree(capacity), _size(0) {}
    
    void insert(const T& val) {
        if (_size >= tree.size()) {
            throw std::overflow_error("Tree is full");
        }
        tree[_size++] = val;
    }
    
    std::optional<int> getParent(int i) const {
        if (i == 0) return std::nullopt;
        return (i - 1) / 2;
    }
    
    std::optional<int> getLeftChild(int i) const {
        int left = 2 * i + 1;
        return (left < _size) ? std::optional<int>(left) : std::nullopt;
    }
    
    std::optional<int> getRightChild(int i) const {
        int right = 2 * i + 2;
        return (right < _size) ? std::optional<int>(right) : std::nullopt;
    }
    
    void display() const {
        std::cout << "Array representation: [";
        for (size_t i = 0; i < _size; i++) {
            std::cout << tree[i].value();
            if (i < _size - 1) std::cout << ", ";
        }
        std::cout << "]" << std::endl;
    }
};

int main() {
    ArrayBinaryTree<int> arrTree;
    for (int val : {1, 2, 3, 4, 5, 6, 7}) {
        arrTree.insert(val);
    }
    
    arrTree.display();  // [1, 2, 3, 4, 5, 6, 7]
    auto parent = arrTree.getParent(3);
    std::cout << "Parent of index 3: " << (parent ? std::to_string(*parent) : "None") << std::endl;  // 1
    auto left = arrTree.getLeftChild(1);
    std::cout << "Left child of index 1: " << (left ? std::to_string(*left) : "None") << std::endl;  // 3
    return 0;
}

// Array Representation (for Complete Binary Trees)
// Parent at index i: children at 2i+1 and 2i+2
// Child at index i: parent at (i-1)/2
import java.util.*;

public class ArrayBinaryTree<T> {
    private Object[] tree;
    private int size;
    
    public ArrayBinaryTree(int capacity) {
        tree = new Object[capacity];
        size = 0;
    }
    
    public void insert(T val) {
        if (size >= tree.length) {
            throw new IllegalStateException("Tree is full");
        }
        tree[size++] = val;
    }
    
    public Integer getParent(int i) {
        if (i == 0) return null;
        return (i - 1) / 2;
    }
    
    public Integer getLeftChild(int i) {
        int left = 2 * i + 1;
        return (left < size) ? left : null;
    }
    
    public Integer getRightChild(int i) {
        int right = 2 * i + 2;
        return (right < size) ? right : null;
    }
    
    public void display() {
        System.out.print("Array representation: [");
        for (int i = 0; i < size; i++) {
            System.out.print(tree[i]);
            if (i < size - 1) System.out.print(", ");
        }
        System.out.println("]");
    }
    
    public static void main(String[] args) {
        ArrayBinaryTree<Integer> arrTree = new ArrayBinaryTree<>(100);
        for (int val : new int[]{1, 2, 3, 4, 5, 6, 7}) {
            arrTree.insert(val);
        }
        
        arrTree.display();  // [1, 2, 3, 4, 5, 6, 7]
        System.out.println("Parent of index 3: " + arrTree.getParent(3));  // 1
        System.out.println("Left child of index 1: " + arrTree.getLeftChild(1));  // 3
    }
}

Tree Traversals

Tree traversal orders: inorder, preorder, postorder, and level-order paths highlighted — Comparison of tree traversal orders: inorder (left-root-right), preorder (root-left-right), postorder (left-right-root), and level-order (BFS)

Traversal Order Comparison on Sample Tree

                            flowchart TD
                                subgraph Tree["Binary Tree"]
                                    A(("1")) --> B(("2"))
                                    A --> C(("3"))
                                    B --> D(("4"))
                                    B --> E(("5"))
                                    C --> F(("6"))
                                    C --> G(("7"))
                                end
                                subgraph Orders["Traversal Results"]
                                    direction LR
                                    IN["Inorder: 4→2→5→1→6→3→7"]
                                    PRE["Preorder: 1→2→4→5→3→6→7"]
                                    POST["Postorder: 4→5→2→6→7→3→1"]
                                    LVL["Level-order: 1→2→3→4→5→6→7"]
                                end

                            When to Use Each Traversal
                            Inorder — produces sorted output for BSTs; used in expression evaluation
Preorder — copy/serialize a tree; prefix expression generation
Postorder — delete tree safely; calculate folder sizes; postfix expressions
Level-order — find shortest path; serialize for BFS; level-by-level printing

                        

DFS Traversals (Depth-First)

# DFS Traversals - Recursive Implementation
# Time: O(n), Space: O(h) where h is height

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

def inorder_recursive(root):
    """Inorder: Left -> Root -> Right (gives sorted order for BST)"""
    result = []
    
    def traverse(node):
        if not node:
            return
        traverse(node.left)
        result.append(node.val)
        traverse(node.right)
    
    traverse(root)
    return result

def preorder_recursive(root):
    """Preorder: Root -> Left -> Right (useful for copying tree)"""
    result = []
    
    def traverse(node):
        if not node:
            return
        result.append(node.val)
        traverse(node.left)
        traverse(node.right)
    
    traverse(root)
    return result

def postorder_recursive(root):
    """Postorder: Left -> Right -> Root (useful for deletion)"""
    result = []
    
    def traverse(node):
        if not node:
            return
        traverse(node.left)
        traverse(node.right)
        result.append(node.val)
    
    traverse(root)
    return result

# Test
#       1
#      / \
#     2   3
#    / \
#   4   5

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print("Inorder:   ", inorder_recursive(root))    # [4, 2, 5, 1, 3]
print("Preorder:  ", preorder_recursive(root))   # [1, 2, 4, 5, 3]
print("Postorder: ", postorder_recursive(root))  # [4, 5, 2, 3, 1]

// DFS Traversals - Recursive Implementation
// Time: O(n), Space: O(h) where h is height
#include <iostream>
#include <vector>

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

void inorderHelper(TreeNode* node, std::vector<int>& result) {
    if (!node) return;
    inorderHelper(node->left, result);
    result.push_back(node->val);
    inorderHelper(node->right, result);
}

void preorderHelper(TreeNode* node, std::vector<int>& result) {
    if (!node) return;
    result.push_back(node->val);
    preorderHelper(node->left, result);
    preorderHelper(node->right, result);
}

void postorderHelper(TreeNode* node, std::vector<int>& result) {
    if (!node) return;
    postorderHelper(node->left, result);
    postorderHelper(node->right, result);
    result.push_back(node->val);
}

std::vector<int> inorderRecursive(TreeNode* root) {
    std::vector<int> result;
    inorderHelper(root, result);
    return result;
}

std::vector<int> preorderRecursive(TreeNode* root) {
    std::vector<int> result;
    preorderHelper(root, result);
    return result;
}

std::vector<int> postorderRecursive(TreeNode* root) {
    std::vector<int> result;
    postorderHelper(root, result);
    return result;
}

int main() {
    TreeNode* 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);
    
    auto printVec = [](const std::vector<int>& v) {
        for (int x : v) std::cout << x << " ";
        std::cout << std::endl;
    };
    
    std::cout << "Inorder:   "; printVec(inorderRecursive(root));    // 4 2 5 1 3
    std::cout << "Preorder:  "; printVec(preorderRecursive(root));   // 1 2 4 5 3
    std::cout << "Postorder: "; printVec(postorderRecursive(root));  // 4 5 2 3 1
    return 0;
}

// DFS Traversals - Recursive Implementation
// Time: O(n), Space: O(h) where h is height
import java.util.*;

public class TreeTraversals {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }
    
    public static List<Integer> inorderRecursive(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorderHelper(root, result);
        return result;
    }
    
    private static void inorderHelper(TreeNode node, List<Integer> result) {
        if (node == null) return;
        inorderHelper(node.left, result);
        result.add(node.val);
        inorderHelper(node.right, result);
    }
    
    public static List<Integer> preorderRecursive(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preorderHelper(root, result);
        return result;
    }
    
    private static void preorderHelper(TreeNode node, List<Integer> result) {
        if (node == null) return;
        result.add(node.val);
        preorderHelper(node.left, result);
        preorderHelper(node.right, result);
    }
    
    public static List<Integer> postorderRecursive(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        postorderHelper(root, result);
        return result;
    }
    
    private static void postorderHelper(TreeNode node, List<Integer> result) {
        if (node == null) return;
        postorderHelper(node.left, result);
        postorderHelper(node.right, result);
        result.add(node.val);
    }
    
    public static void main(String[] args) {
        TreeNode 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);
        
        System.out.println("Inorder:   " + inorderRecursive(root));    // [4, 2, 5, 1, 3]
        System.out.println("Preorder:  " + preorderRecursive(root));   // [1, 2, 4, 5, 3]
        System.out.println("Postorder: " + postorderRecursive(root));  // [4, 5, 2, 3, 1]
    }
}

# DFS Traversals - Iterative Implementation using Stack
# Eliminates recursion stack, explicit control

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

def inorder_iterative(root):
    """Inorder using stack - O(n) time, O(h) space"""
    result = []
    stack = []
    current = root
    
    while current or stack:
        # Go to leftmost node
        while current:
            stack.append(current)
            current = current.left
        
        # Process current node
        current = stack.pop()
        result.append(current.val)
        
        # Move to right subtree
        current = current.right
    
    return result

def preorder_iterative(root):
    """Preorder using stack - O(n) time, O(h) space"""
    if not root:
        return []
    
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        
        # Push right first so left is processed first
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return result

def postorder_iterative(root):
    """Postorder using two stacks - O(n) time, O(n) space"""
    if not root:
        return []
    
    result = []
    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)
    
    while stack2:
        result.append(stack2.pop().val)
    
    return result

# Test
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print("Iterative Inorder:   ", inorder_iterative(root))    # [4, 2, 5, 1, 3]
print("Iterative Preorder:  ", preorder_iterative(root))   # [1, 2, 4, 5, 3]
print("Iterative Postorder: ", postorder_iterative(root))  # [4, 5, 2, 3, 1]

// DFS Traversals - Iterative Implementation using Stack
#include <iostream>
#include <vector>
#include <stack>

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

std::vector<int> inorderIterative(TreeNode* root) {
    std::vector<int> result;
    std::stack<TreeNode*> stk;
    TreeNode* current = root;
    
    while (current || !stk.empty()) {
        while (current) {
            stk.push(current);
            current = current->left;
        }
        current = stk.top(); stk.pop();
        result.push_back(current->val);
        current = current->right;
    }
    return result;
}

std::vector<int> preorderIterative(TreeNode* root) {
    if (!root) return {};
    std::vector<int> result;
    std::stack<TreeNode*> stk;
    stk.push(root);
    
    while (!stk.empty()) {
        TreeNode* node = stk.top(); stk.pop();
        result.push_back(node->val);
        if (node->right) stk.push(node->right);
        if (node->left) stk.push(node->left);
    }
    return result;
}

std::vector<int> postorderIterative(TreeNode* root) {
    if (!root) return {};
    std::vector<int> result;
    std::stack<TreeNode*> stk1, stk2;
    stk1.push(root);
    
    while (!stk1.empty()) {
        TreeNode* node = stk1.top(); stk1.pop();
        stk2.push(node);
        if (node->left) stk1.push(node->left);
        if (node->right) stk1.push(node->right);
    }
    
    while (!stk2.empty()) {
        result.push_back(stk2.top()->val);
        stk2.pop();
    }
    return result;
}

int main() {
    TreeNode* 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);
    
    auto printVec = [](const std::vector<int>& v) {
        for (int x : v) std::cout << x << " ";
        std::cout << std::endl;
    };
    
    std::cout << "Iterative Inorder:   "; printVec(inorderIterative(root));
    std::cout << "Iterative Preorder:  "; printVec(preorderIterative(root));
    std::cout << "Iterative Postorder: "; printVec(postorderIterative(root));
    return 0;
}

// DFS Traversals - Iterative Implementation using Stack
import java.util.*;

public class IterativeTraversals {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }
    
    public static List<Integer> inorderIterative(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode current = root;
        
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            result.add(current.val);
            current = current.right;
        }
        return result;
    }
    
    public static List<Integer> preorderIterative(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
        return result;
    }
    
    public static List<Integer> postorderIterative(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<>();
        if (root == null) return result;
        
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.addFirst(node.val);  // Add to front
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }
        return result;
    }
    
    public static void main(String[] args) {
        TreeNode 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);
        
        System.out.println("Iterative Inorder:   " + inorderIterative(root));
        System.out.println("Iterative Preorder:  " + preorderIterative(root));
        System.out.println("Iterative Postorder: " + postorderIterative(root));
    }
}

BFS Traversal (Level Order)

Level-order traversal visits nodes breadth-first — all nodes at depth 0 (root), then depth 1, then depth 2, and so on. It uses a queue (FIFO): enqueue root, then repeatedly dequeue a node, process it, and enqueue its children. This naturally processes nodes left-to-right within each level. BFS is essential for problems like "minimum depth", "right side view", "zigzag level order", and "connect level pointers".

Key variant — grouped by level: To return results as a list-of-lists (one inner list per level), track the queue's size at the start of each iteration and process exactly that many nodes before moving to the next level.

# Level Order Traversal (BFS) using Queue
from collections import deque

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

def level_order(root):
    """Standard level order - returns flat list"""
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        result.append(node.val)
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return result

def level_order_by_level(root):
    """Level order - returns list of lists (each level separate)"""
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    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

# Test
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)

print("Level Order (flat):", level_order(root))  # [1, 2, 3, 4, 5, 6]
print("Level Order (by level):", level_order_by_level(root))  # [[1], [2, 3], [4, 5, 6]]

// Level Order Traversal (BFS) using Queue
#include <iostream>
#include <vector>
#include <queue>

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

std::vector<int> levelOrder(TreeNode* root) {
    std::vector<int> result;
    if (!root) return result;
    
    std::queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        result.push_back(node->val);
        
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
    return result;
}

std::vector<std::vector<int>> levelOrderByLevel(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> level;
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front();
            q.pop();
            level.push_back(node->val);
            
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        result.push_back(level);
    }
    return result;
}

int main() {
    TreeNode* 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);
    root->right->right = new TreeNode(6);
    
    std::cout << "Level Order (flat): ";
    for (int x : levelOrder(root)) std::cout << x << " ";
    std::cout << std::endl;  // 1 2 3 4 5 6
    
    std::cout << "Level Order (by level): ";
    for (const auto& level : levelOrderByLevel(root)) {
        std::cout << "[";
        for (int i = 0; i < level.size(); i++) {
            std::cout << level[i] << (i < level.size()-1 ? ", " : "");
        }
        std::cout << "] ";
    }
    std::cout << std::endl;  // [1] [2, 3] [4, 5, 6]
    return 0;
}

// Level Order Traversal (BFS) using Queue
import java.util.*;

public class LevelOrderTraversal {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }
    
    public static List<Integer> levelOrder(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            result.add(node.val);
            
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        return result;
    }
    
    public static List<List<Integer>> levelOrderByLevel(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> level = new ArrayList<>();
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(level);
        }
        return result;
    }
    
    public static void main(String[] args) {
        TreeNode 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);
        root.right.right = new TreeNode(6);
        
        System.out.println("Level Order (flat): " + levelOrder(root));
        System.out.println("Level Order (by level): " + levelOrderByLevel(root));
    }
}

# Special Traversals

from collections import deque

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

def zigzag_level_order(root):
    """Zigzag level order (alternating left-right, right-left)"""
    if not root:
        return []
    
    result = []
    queue = deque([root])
    left_to_right = True
    
    while queue:
        level_size = len(queue)
        level = deque()
        
        for _ in range(level_size):
            node = queue.popleft()
            
            if left_to_right:
                level.append(node.val)
            else:
                level.appendleft(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(list(level))
        left_to_right = not left_to_right
    
    return result

def vertical_order(root):
    """Vertical order traversal"""
    if not root:
        return []
    
    from collections import defaultdict
    
    column_map = defaultdict(list)
    queue = deque([(root, 0)])  # (node, column)
    
    while queue:
        node, col = queue.popleft()
        column_map[col].append(node.val)
        
        if node.left:
            queue.append((node.left, col - 1))
        if node.right:
            queue.append((node.right, col + 1))
    
    return [column_map[col] for col in sorted(column_map.keys())]

# Test
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print("Zigzag:", zigzag_level_order(root))  # [[3], [20, 9], [15, 7]]
print("Vertical:", vertical_order(root))    # [[9], [3, 15], [20], [7]]

// Special Traversals - Zigzag and Vertical Order
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>

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

std::vector<std::vector<int>> zigzagLevelOrder(TreeNode* root) {
    std::vector<std::vector<int>> result;
    if (!root) return result;
    
    std::queue<TreeNode*> q;
    q.push(root);
    bool leftToRight = true;
    
    while (!q.empty()) {
        int levelSize = q.size();
        std::deque<int> level;
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front();
            q.pop();
            
            if (leftToRight) level.push_back(node->val);
            else level.push_front(node->val);
            
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        result.push_back(std::vector<int>(level.begin(), level.end()));
        leftToRight = !leftToRight;
    }
    return result;
}

std::vector<std::vector<int>> verticalOrder(TreeNode* root) {
    std::vector<std::vector<int>> result;
    if (!root) return result;
    
    std::map<int, std::vector<int>> columnMap;
    std::queue<std::pair<TreeNode*, int>> q;
    q.push({root, 0});
    
    while (!q.empty()) {
        auto [node, col] = q.front();
        q.pop();
        columnMap[col].push_back(node->val);
        
        if (node->left) q.push({node->left, col - 1});
        if (node->right) q.push({node->right, col + 1});
    }
    
    for (auto& [col, vals] : columnMap) {
        result.push_back(vals);
    }
    return result;
}

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    
    std::cout << "Zigzag: ";
    for (const auto& level : zigzagLevelOrder(root)) {
        std::cout << "[";
        for (int i = 0; i < level.size(); i++) {
            std::cout << level[i] << (i < level.size()-1 ? ", " : "");
        }
        std::cout << "] ";
    }
    std::cout << std::endl;  // [3] [20, 9] [15, 7]
    return 0;
}

// Special Traversals - Zigzag and Vertical Order
import java.util.*;

public class SpecialTraversals {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }
    
    public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean leftToRight = true;
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            LinkedList<Integer> level = new LinkedList<>();
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                
                if (leftToRight) level.addLast(node.val);
                else level.addFirst(node.val);
                
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(level);
            leftToRight = !leftToRight;
        }
        return result;
    }
    
    public static List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        
        TreeMap<Integer, List<Integer>> columnMap = new TreeMap<>();
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> colQueue = new LinkedList<>();
        
        nodeQueue.offer(root);
        colQueue.offer(0);
        
        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();
            int col = colQueue.poll();
            
            columnMap.computeIfAbsent(col, k -> new ArrayList<>()).add(node.val);
            
            if (node.left != null) {
                nodeQueue.offer(node.left);
                colQueue.offer(col - 1);
            }
            if (node.right != null) {
                nodeQueue.offer(node.right);
                colQueue.offer(col + 1);
            }
        }
        
        result.addAll(columnMap.values());
        return result;
    }
    
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        
        System.out.println("Zigzag: " + zigzagLevelOrder(root));  // [[3], [20, 9], [15, 7]]
        System.out.println("Vertical: " + verticalOrder(root));   // [[9], [3, 15], [20], [7]]
    }
}

Tree Properties

Understanding tree dimensions is crucial for complexity analysis and interview problems. Height of a node is the longest path from that node down to a leaf (height of leaf = 0, height of tree = height of root). Depth of a node is the distance from the root down to that node (depth of root = 0). A tree is balanced if for every node, the heights of left and right subtrees differ by at most 1.

Key formulas: A complete binary tree of height \(h\) has between \(2^h\) and \(2^{h+1}-1\) nodes. A full binary tree (every node has 0 or 2 children) with \(n\) internal nodes has \(n+1\) leaves. These properties determine whether operations are \(O(\log n)\) (balanced) or \(O(n)\) (degenerate/skewed).

Binary tree with height, depth, and level annotations for each node — Tree properties visualized: height (longest path to leaf), depth (distance from root), and level of each node

# Tree Properties and Calculations

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

def tree_height(root):
    """Calculate height of tree (edges from root to deepest leaf)"""
    if not root:
        return -1  # Empty tree has height -1
    
    return 1 + max(tree_height(root.left), tree_height(root.right))

def tree_depth(root, target, depth=0):
    """Find depth of a specific node"""
    if not root:
        return -1
    
    if root.val == target:
        return depth
    
    left_depth = tree_depth(root.left, target, depth + 1)
    if left_depth != -1:
        return left_depth
    
    return tree_depth(root.right, target, depth + 1)

def count_nodes(root):
    """Count total nodes in tree"""
    if not root:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)

def count_leaves(root):
    """Count leaf nodes"""
    if not root:
        return 0
    if not root.left and not root.right:
        return 1
    return count_leaves(root.left) + count_leaves(root.right)

def is_balanced(root):
    """Check if tree is height-balanced"""
    def check(node):
        if not node:
            return 0
        
        left_height = check(node.left)
        if left_height == -1:
            return -1
        
        right_height = check(node.right)
        if right_height == -1:
            return -1
        
        if abs(left_height - right_height) > 1:
            return -1
        
        return 1 + max(left_height, right_height)
    
    return check(root) != -1

# Test
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print(f"Height: {tree_height(root)}")     # 2
print(f"Depth of 5: {tree_depth(root, 5)}")  # 2
print(f"Total nodes: {count_nodes(root)}")  # 5
print(f"Leaf nodes: {count_leaves(root)}")  # 3
print(f"Is balanced: {is_balanced(root)}")  # True

// Tree Properties and Calculations
#include <iostream>
#include <algorithm>
#include <cmath>

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

int treeHeight(TreeNode* root) {
    if (!root) return -1;
    return 1 + std::max(treeHeight(root->left), treeHeight(root->right));
}

int treeDepth(TreeNode* root, int target, int depth = 0) {
    if (!root) return -1;
    if (root->val == target) return depth;
    
    int leftDepth = treeDepth(root->left, target, depth + 1);
    if (leftDepth != -1) return leftDepth;
    return treeDepth(root->right, target, depth + 1);
}

int countNodes(TreeNode* root) {
    if (!root) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

int countLeaves(TreeNode* root) {
    if (!root) return 0;
    if (!root->left && !root->right) return 1;
    return countLeaves(root->left) + countLeaves(root->right);
}

int checkBalanced(TreeNode* node) {
    if (!node) return 0;
    int leftH = checkBalanced(node->left);
    if (leftH == -1) return -1;
    int rightH = checkBalanced(node->right);
    if (rightH == -1) return -1;
    if (std::abs(leftH - rightH) > 1) return -1;
    return 1 + std::max(leftH, rightH);
}

bool isBalanced(TreeNode* root) {
    return checkBalanced(root) != -1;
}

int main() {
    TreeNode* 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);
    
    std::cout << "Height: " << treeHeight(root) << std::endl;        // 2
    std::cout << "Depth of 5: " << treeDepth(root, 5) << std::endl;  // 2
    std::cout << "Total nodes: " << countNodes(root) << std::endl;   // 5
    std::cout << "Leaf nodes: " << countLeaves(root) << std::endl;   // 3
    std::cout << "Is balanced: " << (isBalanced(root) ? "True" : "False") << std::endl;  // True
    return 0;
}

// Tree Properties and Calculations
public class TreeProperties {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }
    
    public static int treeHeight(TreeNode root) {
        if (root == null) return -1;
        return 1 + Math.max(treeHeight(root.left), treeHeight(root.right));
    }
    
    public static int treeDepth(TreeNode root, int target, int depth) {
        if (root == null) return -1;
        if (root.val == target) return depth;
        
        int leftDepth = treeDepth(root.left, target, depth + 1);
        if (leftDepth != -1) return leftDepth;
        return treeDepth(root.right, target, depth + 1);
    }
    
    public static int countNodes(TreeNode root) {
        if (root == null) return 0;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
    
    public static int countLeaves(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        return countLeaves(root.left) + countLeaves(root.right);
    }
    
    private static int checkBalanced(TreeNode node) {
        if (node == null) return 0;
        int leftH = checkBalanced(node.left);
        if (leftH == -1) return -1;
        int rightH = checkBalanced(node.right);
        if (rightH == -1) return -1;
        if (Math.abs(leftH - rightH) > 1) return -1;
        return 1 + Math.max(leftH, rightH);
    }
    
    public static boolean isBalanced(TreeNode root) {
        return checkBalanced(root) != -1;
    }
    
    public static void main(String[] args) {
        TreeNode 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);
        
        System.out.println("Height: " + treeHeight(root));        // 2
        System.out.println("Depth of 5: " + treeDepth(root, 5, 0));  // 2
        System.out.println("Total nodes: " + countNodes(root));   // 5
        System.out.println("Leaf nodes: " + countLeaves(root));   // 3
        System.out.println("Is balanced: " + isBalanced(root));   // true
    }
}

# More Tree Properties

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

def max_width(root):
    """Find maximum width (max nodes at any level)"""
    if not root:
        return 0
    
    from collections import deque
    queue = deque([root])
    max_w = 0
    
    while queue:
        level_size = len(queue)
        max_w = max(max_w, level_size)
        
        for _ in range(level_size):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return max_w

def diameter(root):
    """Find diameter (longest path between any two nodes)"""
    max_diameter = [0]
    
    def height(node):
        if not node:
            return 0
        
        left_h = height(node.left)
        right_h = height(node.right)
        
        # Update diameter (path through this node)
        max_diameter[0] = max(max_diameter[0], left_h + right_h)
        
        return 1 + max(left_h, right_h)
    
    height(root)
    return max_diameter[0]

def is_symmetric(root):
    """Check if tree is symmetric (mirror of itself)"""
    def is_mirror(t1, t2):
        if not t1 and not t2:
            return True
        if not t1 or not t2:
            return False
        return (t1.val == t2.val and 
                is_mirror(t1.left, t2.right) and 
                is_mirror(t1.right, t2.left))
    
    return is_mirror(root, root)

# Test
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

print(f"Max width: {max_width(root)}")  # 4
print(f"Diameter: {diameter(root)}")     # 4 (path: 4-2-1-3-7 or similar)

# Symmetric tree test
sym_root = TreeNode(1)
sym_root.left = TreeNode(2)
sym_root.right = TreeNode(2)
sym_root.left.left = TreeNode(3)
sym_root.left.right = TreeNode(4)
sym_root.right.left = TreeNode(4)
sym_root.right.right = TreeNode(3)

print(f"Is symmetric: {is_symmetric(sym_root)}")  # True

// More Tree Properties - Width, Diameter, Symmetric
#include <iostream>
#include <queue>
#include <algorithm>

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

int maxWidth(TreeNode* root) {
    if (!root) return 0;
    std::queue<TreeNode*> q;
    q.push(root);
    int maxW = 0;
    
    while (!q.empty()) {
        int levelSize = q.size();
        maxW = std::max(maxW, levelSize);
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front();
            q.pop();
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return maxW;
}

int diameterHelper(TreeNode* node, int& maxDiam) {
    if (!node) return 0;
    int leftH = diameterHelper(node->left, maxDiam);
    int rightH = diameterHelper(node->right, maxDiam);
    maxDiam = std::max(maxDiam, leftH + rightH);
    return 1 + std::max(leftH, rightH);
}

int diameter(TreeNode* root) {
    int maxDiam = 0;
    diameterHelper(root, maxDiam);
    return maxDiam;
}

bool isMirror(TreeNode* t1, TreeNode* t2) {
    if (!t1 && !t2) return true;
    if (!t1 || !t2) return false;
    return (t1->val == t2->val &&
            isMirror(t1->left, t2->right) &&
            isMirror(t1->right, t2->left));
}

bool isSymmetric(TreeNode* root) {
    return isMirror(root, root);
}

int main() {
    TreeNode* 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);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);
    
    std::cout << "Max width: " << maxWidth(root) << std::endl;  // 4
    std::cout << "Diameter: " << diameter(root) << std::endl;   // 4
    
    // Symmetric tree
    TreeNode* symRoot = new TreeNode(1);
    symRoot->left = new TreeNode(2);
    symRoot->right = new TreeNode(2);
    symRoot->left->left = new TreeNode(3);
    symRoot->left->right = new TreeNode(4);
    symRoot->right->left = new TreeNode(4);
    symRoot->right->right = new TreeNode(3);
    
    std::cout << "Is symmetric: " << (isSymmetric(symRoot) ? "True" : "False") << std::endl;  // True
    return 0;
}

// More Tree Properties - Width, Diameter, Symmetric
import java.util.*;

public class MoreTreeProperties {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }
    
    public static int maxWidth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int maxW = 0;
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            maxW = Math.max(maxW, levelSize);
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return maxW;
    }
    
    private static int[] maxDiam = {0};
    
    private static int diameterHelper(TreeNode node) {
        if (node == null) return 0;
        int leftH = diameterHelper(node.left);
        int rightH = diameterHelper(node.right);
        maxDiam[0] = Math.max(maxDiam[0], leftH + rightH);
        return 1 + Math.max(leftH, rightH);
    }
    
    public static int diameter(TreeNode root) {
        maxDiam[0] = 0;
        diameterHelper(root);
        return maxDiam[0];
    }
    
    private static boolean isMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return true;
        if (t1 == null || t2 == null) return false;
        return (t1.val == t2.val &&
                isMirror(t1.left, t2.right) &&
                isMirror(t1.right, t2.left));
    }
    
    public static boolean isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }
    
    public static void main(String[] args) {
        TreeNode 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);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        
        System.out.println("Max width: " + maxWidth(root));  // 4
        System.out.println("Diameter: " + diameter(root));   // 4
        
        // Symmetric tree
        TreeNode symRoot = new TreeNode(1);
        symRoot.left = new TreeNode(2);
        symRoot.right = new TreeNode(2);
        symRoot.left.left = new TreeNode(3);
        symRoot.left.right = new TreeNode(4);
        symRoot.right.left = new TreeNode(4);
        symRoot.right.right = new TreeNode(3);
        
        System.out.println("Is symmetric: " + isSymmetric(symRoot));  // true
    }
}

Tree Construction

A unique binary tree can be reconstructed from two traversals — but only certain pairs work: preorder + inorder or postorder + inorder. Preorder/postorder alone is NOT sufficient (they can't distinguish left/right children without inorder as a "separator"). The algorithm: (1) the first element of preorder is always the root, (2) find that element in inorder — everything left is the left subtree, everything right is the right subtree, (3) recurse on each half.

Why This Works

Inorder tells you which nodes belong to the left vs right subtree. Preorder/Postorder tells you which node is the root of each subtree. Together, they uniquely identify the tree structure. Use a hash map to find the root's index in inorder in \(O(1)\) — avoiding \(O(n)\) linear search each time, bringing total time from \(O(n^2)\) to \(O(n)\).

Step-by-step tree construction from preorder and inorder traversal arrays — Building a binary tree from preorder and inorder traversals: identifying root, partitioning arrays, and recursively constructing subtrees

# Build Tree from Preorder and Inorder Traversals

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

def build_tree_pre_in(preorder, inorder):
    """
    Construct binary tree from preorder and inorder traversals.
    Time: O(n), Space: O(n)
    """
    if not preorder or not inorder:
        return None
    
    # Create index map for O(1) lookup in inorder
    inorder_map = {val: idx for idx, val in enumerate(inorder)}
    
    def build(pre_start, pre_end, in_start, in_end):
        if pre_start > pre_end:
            return None
        
        # Root is first element in preorder
        root_val = preorder[pre_start]
        root = TreeNode(root_val)
        
        # Find root position in inorder
        root_idx = inorder_map[root_val]
        left_size = root_idx - in_start
        
        # Recursively build left and right subtrees
        root.left = build(pre_start + 1, pre_start + left_size,
                         in_start, root_idx - 1)
        root.right = build(pre_start + left_size + 1, pre_end,
                          root_idx + 1, in_end)
        
        return root
    
    return build(0, len(preorder) - 1, 0, len(inorder) - 1)

# Test
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]

root = build_tree_pre_in(preorder, inorder)

# Verify
def inorder_traversal(root):
    if not root:
        return []
    return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right)

print("Reconstructed inorder:", inorder_traversal(root))  # [9, 3, 15, 20, 7]

// Build Tree from Preorder and Inorder Traversals
// Time: O(n), Space: O(n)
#include <iostream>
#include <vector>
#include <unordered_map>

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

class Solution {
private:
    std::unordered_map<int, int> inorderMap;
    int preIdx = 0;
    
    TreeNode* build(std::vector<int>& preorder, int inStart, int inEnd) {
        if (inStart > inEnd) return nullptr;
        
        int rootVal = preorder[preIdx++];
        TreeNode* root = new TreeNode(rootVal);
        int mid = inorderMap[rootVal];
        
        root->left = build(preorder, inStart, mid - 1);
        root->right = build(preorder, mid + 1, inEnd);
        
        return root;
    }
    
public:
    TreeNode* buildTree(std::vector<int>& preorder, std::vector<int>& inorder) {
        for (int i = 0; i < inorder.size(); i++) {
            inorderMap[inorder[i]] = i;
        }
        preIdx = 0;
        return build(preorder, 0, inorder.size() - 1);
    }
};

void inorderTraversal(TreeNode* root, std::vector<int>& result) {
    if (!root) return;
    inorderTraversal(root->left, result);
    result.push_back(root->val);
    inorderTraversal(root->right, result);
}

int main() {
    std::vector<int> preorder = {3, 9, 20, 15, 7};
    std::vector<int> inorder = {9, 3, 15, 20, 7};
    
    Solution sol;
    TreeNode* root = sol.buildTree(preorder, inorder);
    
    std::vector<int> result;
    inorderTraversal(root, result);
    std::cout << "Reconstructed inorder: ";
    for (int x : result) std::cout << x << " ";
    std::cout << std::endl;  // 9 3 15 20 7
    return 0;
}

// Build Tree from Preorder and Inorder Traversals
// Time: O(n), Space: O(n)
import java.util.*;

public class BuildTreePreIn {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }
    
    private Map<Integer, Integer> inorderMap = new HashMap<>();
    private int preIdx = 0;
    
    private TreeNode build(int[] preorder, int inStart, int inEnd) {
        if (inStart > inEnd) return null;
        
        int rootVal = preorder[preIdx++];
        TreeNode root = new TreeNode(rootVal);
        int mid = inorderMap.get(rootVal);
        
        root.left = build(preorder, inStart, mid - 1);
        root.right = build(preorder, mid + 1, inEnd);
        
        return root;
    }
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        preIdx = 0;
        return build(preorder, 0, inorder.length - 1);
    }
    
    private void inorderTraversal(TreeNode root, List<Integer> result) {
        if (root == null) return;
        inorderTraversal(root.left, result);
        result.add(root.val);
        inorderTraversal(root.right, result);
    }
    
    public static void main(String[] args) {
        int[] preorder = {3, 9, 20, 15, 7};
        int[] inorder = {9, 3, 15, 20, 7};
        
        BuildTreePreIn sol = new BuildTreePreIn();
        TreeNode root = sol.buildTree(preorder, inorder);
        
        List<Integer> result = new ArrayList<>();
        sol.inorderTraversal(root, result);
        System.out.println("Reconstructed inorder: " + result);  // [9, 3, 15, 20, 7]
    }
}

# Build Tree from Inorder and Postorder Traversals

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

def build_tree_in_post(inorder, postorder):
    """
    Construct binary tree from inorder and postorder traversals.
    Time: O(n), Space: O(n)
    """
    if not inorder or not postorder:
        return None
    
    inorder_map = {val: idx for idx, val in enumerate(inorder)}
    post_idx = [len(postorder) - 1]  # Start from last element
    
    def build(in_start, in_end):
        if in_start > in_end:
            return None
        
        # Root is last element in postorder (process right to left)
        root_val = postorder[post_idx[0]]
        post_idx[0] -= 1
        root = TreeNode(root_val)
        
        root_idx = inorder_map[root_val]
        
        # Build right subtree first (because postorder is L-R-Root)
        root.right = build(root_idx + 1, in_end)
        root.left = build(in_start, root_idx - 1)
        
        return root
    
    return build(0, len(inorder) - 1)

# Test
inorder = [9, 3, 15, 20, 7]
postorder = [9, 15, 7, 20, 3]

root = build_tree_in_post(inorder, postorder)

def preorder_traversal(root):
    if not root:
        return []
    return [root.val] + preorder_traversal(root.left) + preorder_traversal(root.right)

print("Reconstructed preorder:", preorder_traversal(root))  # [3, 9, 20, 15, 7]

// Build Tree from Inorder and Postorder Traversals
// Time: O(n), Space: O(n)
#include <iostream>
#include <vector>
#include <unordered_map>

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

class Solution {
private:
    std::unordered_map<int, int> inorderMap;
    int postIdx;
    
    TreeNode* build(std::vector<int>& postorder, int inStart, int inEnd) {
        if (inStart > inEnd) return nullptr;
        
        int rootVal = postorder[postIdx--];
        TreeNode* root = new TreeNode(rootVal);
        int mid = inorderMap[rootVal];
        
        // Build right subtree first (postorder is L-R-Root)
        root->right = build(postorder, mid + 1, inEnd);
        root->left = build(postorder, inStart, mid - 1);
        
        return root;
    }
    
public:
    TreeNode* buildTree(std::vector<int>& inorder, std::vector<int>& postorder) {
        for (int i = 0; i < inorder.size(); i++) {
            inorderMap[inorder[i]] = i;
        }
        postIdx = postorder.size() - 1;
        return build(postorder, 0, inorder.size() - 1);
    }
};

void preorderTraversal(TreeNode* root, std::vector<int>& result) {
    if (!root) return;
    result.push_back(root->val);
    preorderTraversal(root->left, result);
    preorderTraversal(root->right, result);
}

int main() {
    std::vector<int> inorder = {9, 3, 15, 20, 7};
    std::vector<int> postorder = {9, 15, 7, 20, 3};
    
    Solution sol;
    TreeNode* root = sol.buildTree(inorder, postorder);
    
    std::vector<int> result;
    preorderTraversal(root, result);
    std::cout << "Reconstructed preorder: ";
    for (int x : result) std::cout << x << " ";
    std::cout << std::endl;  // 3 9 20 15 7
    return 0;
}

// Build Tree from Inorder and Postorder Traversals
// Time: O(n), Space: O(n)
import java.util.*;

public class BuildTreeInPost {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }
    
    private Map<Integer, Integer> inorderMap = new HashMap<>();
    private int postIdx;
    
    private TreeNode build(int[] postorder, int inStart, int inEnd) {
        if (inStart > inEnd) return null;
        
        int rootVal = postorder[postIdx--];
        TreeNode root = new TreeNode(rootVal);
        int mid = inorderMap.get(rootVal);
        
        // Build right subtree first (postorder is L-R-Root)
        root.right = build(postorder, mid + 1, inEnd);
        root.left = build(postorder, inStart, mid - 1);
        
        return root;
    }
    
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        postIdx = postorder.length - 1;
        return build(postorder, 0, inorder.length - 1);
    }
    
    private void preorderTraversal(TreeNode root, List<Integer> result) {
        if (root == null) return;
        result.add(root.val);
        preorderTraversal(root.left, result);
        preorderTraversal(root.right, result);
    }
    
    public static void main(String[] args) {
        int[] inorder = {9, 3, 15, 20, 7};
        int[] postorder = {9, 15, 7, 20, 3};
        
        BuildTreeInPost sol = new BuildTreeInPost();
        TreeNode root = sol.buildTree(inorder, postorder);
        
        List<Integer> result = new ArrayList<>();
        sol.preorderTraversal(root, result);
        System.out.println("Reconstructed preorder: " + result);  // [3, 9, 20, 15, 7]
    }
}

LeetCode Practice Problems

Easy 104. Maximum Depth of Binary Tree

Find the maximum depth (height) of a binary tree.

# LeetCode 104 - Maximum Depth of Binary Tree
# Time: O(n), Space: O(h)

def maxDepth(root):
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

# Iterative BFS solution
from collections import deque

def maxDepth_bfs(root):
    if not root:
        return 0
    
    depth = 0
    queue = deque([root])
    
    while queue:
        depth += 1
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return depth

// LeetCode 104 - Maximum Depth of Binary Tree
// Time: O(n), Space: O(h)
#include <algorithm>
#include <queue>

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

class Solution {
public:
    // Recursive
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        return 1 + std::max(maxDepth(root->left), maxDepth(root->right));
    }
    
    // Iterative BFS
    int maxDepthBFS(TreeNode* root) {
        if (!root) return 0;
        int depth = 0;
        std::queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            depth++;
            int levelSize = q.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front();
                q.pop();
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return depth;
    }
};

// LeetCode 104 - Maximum Depth of Binary Tree
// Time: O(n), Space: O(h)
import java.util.*;

class Solution {
    // Recursive
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
    
    // Iterative BFS
    public int maxDepthBFS(TreeNode root) {
        if (root == null) return 0;
        int depth = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            depth++;
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return depth;
    }
}

Easy 226. Invert Binary Tree

Invert (mirror) a binary tree.

# LeetCode 226 - Invert Binary Tree
# Time: O(n), Space: O(h)

def invertTree(root):
    if not root:
        return None
    
    # Swap children
    root.left, root.right = root.right, root.left
    
    # Recursively invert subtrees
    invertTree(root.left)
    invertTree(root.right)
    
    return root

// LeetCode 226 - Invert Binary Tree
// Time: O(n), Space: O(h)
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return nullptr;
        
        // Swap children
        std::swap(root->left, root->right);
        
        // Recursively invert subtrees
        invertTree(root->left);
        invertTree(root->right);
        
        return root;
    }
};

// LeetCode 226 - Invert Binary Tree
// Time: O(n), Space: O(h)

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        
        // Swap children
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        
        // Recursively invert subtrees
        invertTree(root.left);
        invertTree(root.right);
        
        return root;
    }
}

Easy 100. Same Tree

Check if two binary trees are identical.

# LeetCode 100 - Same Tree
# Time: O(n), Space: O(h)

def isSameTree(p, q):
    # Both empty
    if not p and not q:
        return True
    
    # One empty, one not
    if not p or not q:
        return False
    
    # Both non-empty - check value and children
    return (p.val == q.val and 
            isSameTree(p.left, q.left) and 
            isSameTree(p.right, q.right))

// LeetCode 100 - Same Tree
// Time: O(n), Space: O(h)
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q) return true;
        if (!p || !q) return false;
        return (p->val == q->val &&
                isSameTree(p->left, q->left) &&
                isSameTree(p->right, q->right));
    }
};

// LeetCode 100 - Same Tree
// Time: O(n), Space: O(h)

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        return (p.val == q.val &&
                isSameTree(p.left, q.left) &&
                isSameTree(p.right, q.right));
    }
}

Medium 236. Lowest Common Ancestor

Find the lowest common ancestor (LCA) of two nodes.

# LeetCode 236 - Lowest Common Ancestor of a Binary Tree
# Time: O(n), Space: O(h)

def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q:
        return root
    
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    
    # If both sides return non-null, root is LCA
    if left and right:
        return root
    
    # Otherwise, return the non-null side
    return left if left else right

// LeetCode 236 - Lowest Common Ancestor of a Binary Tree
// Time: O(n), Space: O(h)
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    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 (left && right) return root;
        return left ? left : right;
    }
};

// LeetCode 236 - Lowest Common Ancestor of a Binary Tree
// Time: O(n), Space: O(h)

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        if (left != null && right != null) return root;
        return left != null ? left : right;
    }
}

Medium 105. Construct Binary Tree from Preorder and Inorder

Build tree from preorder and inorder traversals.

# LeetCode 105 - Construct Binary Tree from Preorder and Inorder
# Time: O(n), Space: O(n)

def buildTree(preorder, inorder):
    if not preorder:
        return None
    
    inorder_map = {val: idx for idx, val in enumerate(inorder)}
    pre_idx = [0]
    
    def build(in_start, in_end):
        if in_start > in_end:
            return None
        
        root_val = preorder[pre_idx[0]]
        pre_idx[0] += 1
        root = TreeNode(root_val)
        
        mid = inorder_map[root_val]
        root.left = build(in_start, mid - 1)
        root.right = build(mid + 1, in_end)
        
        return root
    
    return build(0, len(inorder) - 1)

// LeetCode 105 - Construct Binary Tree from Preorder and Inorder
// Time: O(n), Space: O(n)
#include <vector>
#include <unordered_map>

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

class Solution {
private:
    std::unordered_map<int, int> inorderMap;
    int preIdx = 0;
    
    TreeNode* build(std::vector<int>& preorder, int inStart, int inEnd) {
        if (inStart > inEnd) return nullptr;
        
        int rootVal = preorder[preIdx++];
        TreeNode* root = new TreeNode(rootVal);
        int mid = inorderMap[rootVal];
        
        root->left = build(preorder, inStart, mid - 1);
        root->right = build(preorder, mid + 1, inEnd);
        
        return root;
    }
    
public:
    TreeNode* buildTree(std::vector<int>& preorder, std::vector<int>& inorder) {
        for (int i = 0; i < inorder.size(); i++) {
            inorderMap[inorder[i]] = i;
        }
        preIdx = 0;
        return build(preorder, 0, inorder.size() - 1);
    }
};

// LeetCode 105 - Construct Binary Tree from Preorder and Inorder
// Time: O(n), Space: O(n)
import java.util.*;

class Solution {
    private Map<Integer, Integer> inorderMap = new HashMap<>();
    private int preIdx = 0;
    
    private TreeNode build(int[] preorder, int inStart, int inEnd) {
        if (inStart > inEnd) return null;
        
        int rootVal = preorder[preIdx++];
        TreeNode root = new TreeNode(rootVal);
        int mid = inorderMap.get(rootVal);
        
        root.left = build(preorder, inStart, mid - 1);
        root.right = build(preorder, mid + 1, inEnd);
        
        return root;
    }
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        preIdx = 0;
        return build(preorder, 0, inorder.length - 1);
    }
}

Medium 114. Flatten Binary Tree to Linked List

Flatten tree to linked list in-place (preorder).

# LeetCode 114 - Flatten Binary Tree to Linked List
# Time: O(n), Space: O(1) - Morris-like approach

def flatten(root):
    current = root
    
    while current:
        if current.left:
            # Find rightmost node in left subtree
            rightmost = current.left
            while rightmost.right:
                rightmost = rightmost.right
            
            # Connect rightmost to current's right
            rightmost.right = current.right
            
            # Move left subtree to right
            current.right = current.left
            current.left = None
        
        current = current.right

// LeetCode 114 - Flatten Binary Tree to Linked List
// Time: O(n), Space: O(1) - Morris-like approach
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* current = root;
        
        while (current) {
            if (current->left) {
                // Find rightmost node in left subtree
                TreeNode* rightmost = current->left;
                while (rightmost->right) {
                    rightmost = rightmost->right;
                }
                
                // Connect rightmost to current's right
                rightmost->right = current->right;
                
                // Move left subtree to right
                current->right = current->left;
                current->left = nullptr;
            }
            current = current->right;
        }
    }
};

// LeetCode 114 - Flatten Binary Tree to Linked List
// Time: O(n), Space: O(1) - Morris-like approach

class Solution {
    public void flatten(TreeNode root) {
        TreeNode current = root;
        
        while (current != null) {
            if (current.left != null) {
                // Find rightmost node in left subtree
                TreeNode rightmost = current.left;
                while (rightmost.right != null) {
                    rightmost = rightmost.right;
                }
                
                // Connect rightmost to current's right
                rightmost.right = current.right;
                
                // Move left subtree to right
                current.right = current.left;
                current.left = null;
            }
            current = current.right;
        }
    }
}

Hard 124. Binary Tree Maximum Path Sum

Find the maximum path sum (path can start and end anywhere).

# LeetCode 124 - Binary Tree Maximum Path Sum
# Time: O(n), Space: O(h)

def maxPathSum(root):
    max_sum = [float('-inf')]
    
    def max_gain(node):
        if not node:
            return 0
        
        # Get max gain from left and right (ignore negative)
        left_gain = max(max_gain(node.left), 0)
        right_gain = max(max_gain(node.right), 0)
        
        # Path through this node
        path_sum = node.val + left_gain + right_gain
        max_sum[0] = max(max_sum[0], path_sum)
        
        # Return max gain including this node (can only go one way)
        return node.val + max(left_gain, right_gain)
    
    max_gain(root)
    return max_sum[0]

// LeetCode 124 - Binary Tree Maximum Path Sum
// Time: O(n), Space: O(h)
#include <algorithm>
#include <climits>

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

class Solution {
private:
    int maxSum = INT_MIN;
    
    int maxGain(TreeNode* node) {
        if (!node) return 0;
        
        // Get max gain from left and right (ignore negative)
        int leftGain = std::max(maxGain(node->left), 0);
        int rightGain = std::max(maxGain(node->right), 0);
        
        // Path through this node
        int pathSum = node->val + leftGain + rightGain;
        maxSum = std::max(maxSum, pathSum);
        
        // Return max gain including this node (can only go one way)
        return node->val + std::max(leftGain, rightGain);
    }
    
public:
    int maxPathSum(TreeNode* root) {
        maxSum = INT_MIN;
        maxGain(root);
        return maxSum;
    }
};

// LeetCode 124 - Binary Tree Maximum Path Sum
// Time: O(n), Space: O(h)

class Solution {
    private int maxSum = Integer.MIN_VALUE;
    
    private int maxGain(TreeNode node) {
        if (node == null) return 0;
        
        // Get max gain from left and right (ignore negative)
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);
        
        // Path through this node
        int pathSum = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, pathSum);
        
        // Return max gain including this node (can only go one way)
        return node.val + Math.max(leftGain, rightGain);
    }
    
    public int maxPathSum(TreeNode root) {
        maxSum = Integer.MIN_VALUE;
        maxGain(root);
        return maxSum;
    }
}

Quick Check — Test Yourself

Write the in-order traversal of a binary tree iteratively (without recursion).
Given a binary tree, determine whether it is height-balanced in \(O(n)\).
Find the lowest common ancestor (LCA) of two nodes in a binary tree.

Common Bugs

Confusing height and depth: Height = edges from node to deepest leaf. Depth = edges from root to node. A single-node tree has height 0.
Missing null check in recursive tree code: Every recursive tree function needs a base case: if not node: return .... Forgetting this causes NullPointerException.
Level-order traversal forgetting to track levels: BFS gives level-order, but tracking which level each node is on requires processing the queue in level-sized batches.

Interview Lens

Tree problems almost always have a clean recursive solution. The trick is thinking about what each node needs to “return up” to its parent (height, size, sum, is_valid flag). If you find yourself passing state downward, you’re usually in DFS with parameters; if returning state upward, you’re in post-order recursion.

Production Lens

File systems are trees (directories are internal nodes, files are leaves). DOM (browser) is a tree. JSON/XML are trees. Parsers produce abstract syntax trees (ASTs). Every hierarchical data model maps to a tree — tree algorithms appear in more production code than most engineers realise.

Next in the Series

In Part 10: BST, AVL & Red-Black Trees, we'll impose ordering on tree structure — turning a general tree into a search structure, then exploring how AVL and Red-Black trees maintain \(O(\log n)\) guarantees through rotations.

Complete DSA Series Part 9: Trees

Table of Contents

FAANG Interview Prep

Foundations, Memory & Complexity

Recursion Complete Guide

Arrays & Array ADT

Strings

Matrices

Linked Lists

Stack

Queue