Complete DSA Series Part 9: Trees

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 Terminology

Types of Binary Trees

Tree Representation

# 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}")

C++

// 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;
}

Java

// 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

C++

// 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;
}

Java

// 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

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]

C++

// 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;
}

Java

// 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]

C++

// 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;
}

Java

// 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 (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]]

C++

// 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;
}

Java

// 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]]

C++

// 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;
}

Java

// 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

# 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

C++

// 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;
}

Java

// 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

C++

// 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;
}

Java

// 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

# 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]

C++

// 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;
}

Java

// 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]

C++

// 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;
}

Java

// 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

# 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;
    }
}

# 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;
    }
}

# 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));
    }
}

# 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;
    }
}

# 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);
    }
}

# 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;
        }
    }
}

# 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;
    }
}