Tree Basics & Traversals

Before diving into code, let's learn the vocabulary of trees. These terms will appear constantly in interviews and documentation, so understanding them is essential for clear communication.

                    ┌───────────────────────────────────────────────────┐
                    │           TREE TERMINOLOGY DIAGRAM                │
                    └───────────────────────────────────────────────────┘

          Depth 0 (Level 0)           [A] ← ROOT (no parent)
                                     /   \
          Depth 1 (Level 1)       [B]     [C] ← INTERNAL NODES (have children)
                                 /   \       \
          Depth 2 (Level 2)   [D]    [E]     [F] ← LEAF NODES (no children)
                              /
          Depth 3 (Level 3) [G] ← Deepest LEAF

                    ┌───────────────────────────────────────────────────┐
                    │  HEIGHT of tree = 3 (longest path from root)      │
                    │  HEIGHT of node B = 2 (path to deepest leaf G)    │
                    │  DEPTH of node E = 2 (distance from root)         │
                    │  B & C are SIBLINGS (same parent A)               │
                    │  A is PARENT of B, B is CHILD of A                │
                    │  Subtree rooted at B: {B, D, E, G}                │
                    └───────────────────────────────────────────────────┘
              

Every tree is built from nodes. In Java, we create a simple class to represent each node, storing its value and pointers to its children. This is the foundation for all tree operations.

class TreeNode {
    int val;           // The data stored in this node
    TreeNode left;     // Reference to left child (or null)
    TreeNode right;    // Reference to right child (or null)
}

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

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

// Building this tree:
//        1
//       / \
//      2   3
//     / \
//    4   5

TreeNode root = new TreeNode(1);      // Create root
root.left = new TreeNode(2);          // Attach left child
root.right = new TreeNode(3);         // Attach right child
root.left.left = new TreeNode(4);     // Attach grandchildren
root.left.right = new TreeNode(5);

// Same tree built in one expression
TreeNode root2 = new TreeNode(1,
    new TreeNode(2,
        new TreeNode(4),
        new TreeNode(5)),
    new TreeNode(3)
);

Depth-First Search (DFS) explores a tree by going as deep as possible before backtracking. There are three ways to visit nodes, differing only in when you process the current node.

Recursive Implementation

// Inorder: Left → Root → Right
void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    System.out.print(root.val + " ");
    inorder(root.right);
}

// Preorder: Root → Left → Right
void preorder(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val + " ");
    preorder(root.left);
    preorder(root.right);
}

// Postorder: Left → Right → Root
void postorder(TreeNode root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    System.out.print(root.val + " ");
}

// Example tree:    1
//                 / \
//                2   3
//               / \
//              4   5
// Inorder:   4, 2, 5, 1, 3
// Preorder:  1, 2, 4, 5, 3
// Postorder: 4, 5, 2, 3, 1

Iterative with Stack

// Iterative Inorder
List inorderIterative(TreeNode root) {
    List result = new ArrayList<>();
    Stack stack = new Stack<>();
    TreeNode curr = root;
    
    while (curr != null || !stack.isEmpty()) {
        // Go left as far as possible
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        // Process current node
        curr = stack.pop();
        result.add(curr.val);
        // Go right
        curr = curr.right;
    }
    
    return result;
}

// Iterative Preorder
List preorderIterative(TreeNode root) {
    List result = new ArrayList<>();
    if (root == null) return result;
    
    Stack stack = new Stack<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);
        
        // Push right first so left is processed first
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    
    return result;
}

// Iterative Postorder (using reverse preorder trick)
List postorderIterative(TreeNode root) {
    LinkedList result = new LinkedList<>();
    if (root == null) return result;
    
    Stack stack = new Stack<>();
    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;
}

While DFS goes deep, Breadth-First Search (BFS) explores level by level. It visits all nodes at depth 0, then all at depth 1, and so on. This is perfect for problems involving levels or shortest paths.

// Basic Level Order - returns list of lists
List> levelOrder(TreeNode root) {
    List> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List currentLevel = new ArrayList<>();
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            currentLevel.add(node.val);
            
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        
        result.add(currentLevel);
    }
    
    return result;
}

// Example:     3
//             / \
//            9  20
//              /  \
//             15   7
// Output: [[3], [9,20], [15,7]]

// Zigzag Level Order
List> zigzagLevelOrder(TreeNode root) {
    List> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue queue = new LinkedList<>();
    queue.offer(root);
    boolean leftToRight = true;
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        LinkedList level = new LinkedList<>();
        
        for (int i = 0; i < size; 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;
}

Trees have many properties we need to compute: height, depth, balance, symmetry. These functions form the building blocks for more complex tree algorithms and appear frequently in interviews.

// Maximum Depth (Height)
int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

// Minimum Depth
int minDepth(TreeNode root) {
    if (root == null) return 0;
    if (root.left == null) return 1 + minDepth(root.right);
    if (root.right == null) return 1 + minDepth(root.left);
    return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}

// Count Total Nodes
int countNodes(TreeNode root) {
    if (root == null) return 0;
    return 1 + countNodes(root.left) + countNodes(root.right);
}

// Check if Balanced (height differs by at most 1)
boolean isBalanced(TreeNode root) {
    return height(root) != -1;
}

int height(TreeNode root) {
    if (root == null) return 0;
    
    int leftHeight = height(root.left);
    if (leftHeight == -1) return -1;
    
    int rightHeight = height(root.right);
    if (rightHeight == -1) return -1;
    
    if (Math.abs(leftHeight - rightHeight) > 1) return -1;
    
    return 1 + Math.max(leftHeight, rightHeight);
}

// Check if Symmetric
boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
}

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

// Check if Same Tree
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);
}

Master these reusable code templates. They appear in 80% of tree problems on coding interviews. Copy, adapt, and conquer!

Basic Recursive Traversal

// Template: Process all nodes in tree
void traverse(TreeNode root) {
    if (root == null) return;  // Base case
    
    // PREORDER: Process here (before children)
    // Example: print(root.val);
    
    traverse(root.left);   // Recurse left
    
    // INORDER: Process here (between children)
    // Example: add to sorted list for BST
    
    traverse(root.right);  // Recurse right
    
    // POSTORDER: Process here (after children)
    // Example: delete node safely
}

// Example: Print all values (preorder)
void printAll(TreeNode root) {
    if (root == null) return;
    System.out.println(root.val);  // Process
    printAll(root.left);
    printAll(root.right);
}

When to Use Each Order:

// PREORDER: Clone/Copy a tree
TreeNode cloneTree(TreeNode root) {
    if (root == null) return null;
    TreeNode copy = new TreeNode(root.val);  // Create copy FIRST
    copy.left = cloneTree(root.left);        // Then clone children
    copy.right = cloneTree(root.right);
    return copy;
}

// INORDER: Get sorted elements from BST
void getSorted(TreeNode root, List result) {
    if (root == null) return;
    getSorted(root.left, result);      // All smaller values first
    result.add(root.val);              // Current value in middle
    getSorted(root.right, result);     // All larger values last
}

// POSTORDER: Calculate height (need children's heights first)
int height(TreeNode root) {
    if (root == null) return 0;
    int leftH = height(root.left);     // Get left height first
    int rightH = height(root.right);   // Get right height first
    return 1 + Math.max(leftH, rightH); // Now can compute this node's height
}

Return Value from Subtrees

// Template: Compute something from subtrees
int compute(TreeNode root) {
    if (root == null) return BASE_VALUE;  // What to return for empty tree?
    
    int leftResult = compute(root.left);   // Get result from left subtree
    int rightResult = compute(root.right); // Get result from right subtree
    
    // Combine: How to merge left, right, and current node?
    return COMBINE(leftResult, rightResult, root.val);
}

// Example: Count all nodes
int countNodes(TreeNode root) {
    if (root == null) return 0;
    int left = countNodes(root.left);
    int right = countNodes(root.right);
    return left + right + 1;  // Both subtrees + this node
}

// Example: Sum all values
int sumNodes(TreeNode root) {
    if (root == null) return 0;
    return root.val + sumNodes(root.left) + sumNodes(root.right);
}

// Example: Maximum value
int maxValue(TreeNode root) {
    if (root == null) return Integer.MIN_VALUE;
    int leftMax = maxValue(root.left);
    int rightMax = maxValue(root.right);
    return Math.max(root.val, Math.max(leftMax, rightMax));
}

// Example: Height/Depth
int height(TreeNode root) {
    if (root == null) return 0;  // or -1 depending on definition
    return 1 + Math.max(height(root.left), height(root.right));
}

Two-Node Comparison

// Template: Compare two nodes/trees simultaneously
boolean compare(TreeNode node1, TreeNode node2) {
    // Both null: trees match at this point
    if (node1 == null && node2 == null) return true;
    
    // One null, other not: structure differs
    if (node1 == null || node2 == null) return false;
    
    // Both non-null: check current + recurse
    // Customize comparison logic here
    return node1.val == node2.val && 
           compare(node1.left, node2.left) &&
           compare(node1.right, node2.right);
}

// Example: Same Tree
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);
}

// Example: Symmetric Tree (mirror comparison)
boolean isSymmetric(TreeNode root) {
    return isMirror(root, root);
}

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) &&   // Cross-compare!
           isMirror(t1.right, t2.left);
}

// Example: Is Subtree
boolean isSubtree(TreeNode root, TreeNode subRoot) {
    if (root == null) return false;
    if (isSameTree(root, subRoot)) return true;
    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}

Level-Order (BFS) Pattern

// Template: Process tree level by level
List> levelOrder(TreeNode root) {
    List> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int levelSize = queue.size();  // CRUCIAL: snapshot before loop
        List currentLevel = new ArrayList<>();
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            
            // PROCESS NODE HERE
            currentLevel.add(node.val);
            
            // Add children for next level
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        
        result.add(currentLevel);
    }
    return result;
}

// Variation: Right Side View (last of each level)
List rightSideView(TreeNode root) {
    List result = new ArrayList<>();
    if (root == null) return result;
    
    Queue queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (i == size - 1) result.add(node.val);  // Last node
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
    return result;
}

// Variation: Zigzag (alternate direction)
List> zigzagLevelOrder(TreeNode root) {
    List> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue queue = new LinkedList<>();
    queue.offer(root);
    boolean leftToRight = true;
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        LinkedList level = new LinkedList<>();
        
        for (int i = 0; i < size; 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;  // Flip direction
    }
    return result;
}

Path Problems

// Template: Find/Track paths in tree
// Pattern 1: Root-to-Leaf paths
List> allPaths = new ArrayList<>();

void findPaths(TreeNode root, List currentPath) {
    if (root == null) return;
    
    currentPath.add(root.val);
    
    if (root.left == null && root.right == null) {
        // Reached leaf: save path copy
        allPaths.add(new ArrayList<>(currentPath));
    } else {
        findPaths(root.left, currentPath);
        findPaths(root.right, currentPath);
    }
    
    currentPath.remove(currentPath.size() - 1);  // Backtrack!
}

// Example: Path Sum (does any root-to-leaf path sum to target?)
boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;
    
    // Leaf node: check if remaining sum equals node value
    if (root.left == null && root.right == null) {
        return root.val == targetSum;
    }
    
    // Recurse with reduced target
    return hasPathSum(root.left, targetSum - root.val) ||
           hasPathSum(root.right, targetSum - root.val);
}

// Example: All paths with given sum
List> pathSum(TreeNode root, int targetSum) {
    List> result = new ArrayList<>();
    findPathsWithSum(root, targetSum, new ArrayList<>(), result);
    return result;
}

void findPathsWithSum(TreeNode node, int remaining, 
                      List path, List> result) {
    if (node == null) return;
    
    path.add(node.val);
    
    if (node.left == null && node.right == null && remaining == node.val) {
        result.add(new ArrayList<>(path));
    }
    
    findPathsWithSum(node.left, remaining - node.val, path, result);
    findPathsWithSum(node.right, remaining - node.val, path, result);
    
    path.remove(path.size() - 1);  // Backtrack
}

// Pattern 2: Maximum Path Sum (any-to-any, harder)
int maxPathSum = Integer.MIN_VALUE;

int maxPathSum(TreeNode root) {
    maxPathSum = Integer.MIN_VALUE;
    maxGain(root);
    return maxPathSum;
}

int maxGain(TreeNode node) {
    if (node == null) return 0;
    
    // Max gain from left/right (ignore negative paths)
    int leftGain = Math.max(maxGain(node.left), 0);
    int rightGain = Math.max(maxGain(node.right), 0);
    
    // Path through this node as highest point
    int pathThroughNode = node.val + leftGain + rightGain;
    maxPathSum = Math.max(maxPathSum, pathThroughNode);
    
    // Return max gain if this node is part of path to ancestor
    return node.val + Math.max(leftGain, rightGain);
}

Tree Construction

// Template: Build tree from traversals
// Build from Preorder + Inorder
int preorderIndex = 0;
Map inorderMap = new HashMap<>();

TreeNode buildTree(int[] preorder, int[] inorder) {
    preorderIndex = 0;
    for (int i = 0; i < inorder.length; i++) {
        inorderMap.put(inorder[i], i);
    }
    return buildTreeHelper(preorder, 0, inorder.length - 1);
}

TreeNode buildTreeHelper(int[] preorder, int left, int right) {
    if (left > right) return null;
    
    int rootVal = preorder[preorderIndex++];
    TreeNode root = new TreeNode(rootVal);
    
    int inorderIndex = inorderMap.get(rootVal);
    
    root.left = buildTreeHelper(preorder, left, inorderIndex - 1);
    root.right = buildTreeHelper(preorder, inorderIndex + 1, right);
    
    return root;
}

// Build from level-order array (LeetCode format)
TreeNode buildFromArray(Integer[] arr) {
    if (arr == null || arr.length == 0 || arr[0] == null) return null;
    
    TreeNode root = new TreeNode(arr[0]);
    Queue queue = new LinkedList<>();
    queue.offer(root);
    int i = 1;
    
    while (!queue.isEmpty() && i < arr.length) {
        TreeNode node = queue.poll();
        
        if (i < arr.length && arr[i] != null) {
            node.left = new TreeNode(arr[i]);
            queue.offer(node.left);
        }
        i++;
        
        if (i < arr.length && arr[i] != null) {
            node.right = new TreeNode(arr[i]);
            queue.offer(node.right);
        }
        i++;
    }
    return root;
}

Serialization

// Template: Convert tree to string and back
// Preorder with null markers
public String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    serializeHelper(root, sb);
    return sb.toString();
}

void serializeHelper(TreeNode node, StringBuilder sb) {
    if (node == null) {
        sb.append("null,");
        return;
    }
    sb.append(node.val).append(",");
    serializeHelper(node.left, sb);
    serializeHelper(node.right, sb);
}

public TreeNode deserialize(String data) {
    String[] nodes = data.split(",");
    Queue queue = new LinkedList<>(Arrays.asList(nodes));
    return deserializeHelper(queue);
}

TreeNode deserializeHelper(Queue queue) {
    String val = queue.poll();
    if (val.equals("null")) return null;
    
    TreeNode node = new TreeNode(Integer.parseInt(val));
    node.left = deserializeHelper(queue);
    node.right = deserializeHelper(queue);
    return node;
}

// Example serialized: "1,2,null,null,3,4,null,null,5,null,null"
// Represents:
//       1
//      / \
//     2   3
//        / \
//       4   5

Even experienced programmers make these mistakes. Learn them now to avoid debugging headaches later!

// WRONG: NullPointerException if root is null
int height(TreeNode root) {
    return 1 + Math.max(height(root.left), 
                        height(root.right));
}

// CORRECT: Always check null first
int height(TreeNode root) {
    if (root == null) return 0;  // Base case!
    return 1 + Math.max(height(root.left), 
                        height(root.right));
}

// WRONG: Returns null even when found
TreeNode search(TreeNode root, int val) {
    if (root == null) return null;
    if (root.val == val) return root;
    search(root.left, val);   // Lost!
    search(root.right, val);  // Lost!
    return null;
}

// CORRECT: Return the recursive result
TreeNode search(TreeNode root, int val) {
    if (root == null) return null;
    if (root.val == val) return root;
    TreeNode left = search(root.left, val);
    if (left != null) return left;
    return search(root.right, val);
}

// WRONG: All paths point to same list!
void findPaths(TreeNode node, List path, 
               List> result) {
    if (node == null) return;
    path.add(node.val);
    if (isLeaf(node)) {
        result.add(path);  // DANGER: reference!
    }
    findPaths(node.left, path, result);
    findPaths(node.right, path, result);
    path.remove(path.size() - 1);
}

// CORRECT: Add a copy of the path
if (isLeaf(node)) {
    result.add(new ArrayList<>(path));  // Copy!
}

// WRONG: Mixes nodes from different levels
while (!queue.isEmpty()) {
    TreeNode node = queue.poll();
    currentLevel.add(node.val);
    // Where does one level end?
    if (node.left != null) 
        queue.offer(node.left);
    if (node.right != null) 
        queue.offer(node.right);
}

// CORRECT: Capture size BEFORE loop
while (!queue.isEmpty()) {
    int levelSize = queue.size();  // Snapshot!
    for (int i = 0; i < levelSize; i++) {
        TreeNode node = queue.poll();
        currentLevel.add(node.val);
        if (node.left != null) 
            queue.offer(node.left);
        if (node.right != null) 
            queue.offer(node.right);
    }
    result.add(currentLevel);
}

// WRONG: Right child processed first!
Stack stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
    TreeNode node = stack.pop();
    result.add(node.val);
    if (node.left != null) 
        stack.push(node.left);
    if (node.right != null) 
        stack.push(node.right);
}
// Output: Root, Right, Left (wrong!)

// CORRECT: Push right FIRST so left pops first
if (node.right != null) 
    stack.push(node.right);
if (node.left != null) 
    stack.push(node.left);
// Output: Root, Left, Right (correct!)

// Height of null = -1, single node = 0
int heightV1(TreeNode root) {
    if (root == null) return -1;
    return 1 + Math.max(heightV1(root.left), 
                        heightV1(root.right));
}

// Height of null = 0, single node = 1
int heightV2(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(heightV2(root.left), 
                        heightV2(root.right));
}
// TIP: LeetCode typically uses this!

Understanding complexity is crucial for interviews. Know these by heart!

Height in Different Tree Types

// Height Analysis
// n = number of nodes, h = height

/*
 * BALANCED BINARY TREE (AVL, Red-Black):
 *     Height h = O(log n)
 *     Example: n=7 nodes → h=2
 *         1
 *       /   \
 *      2     3
 *     / \   / \
 *    4   5 6   7
 * 
 * COMPLETE BINARY TREE:
 *     Height h = floor(log₂(n))
 *     All levels full except possibly last
 * 
 * SKEWED TREE (worst case):
 *     Height h = O(n)
 *     Example: n=4 nodes → h=3
 *     1
 *      \
 *       2
 *        \
 *         3
 *          \
 *           4
 * 
 * PERFECT BINARY TREE:
 *     Nodes n = 2^(h+1) - 1
 *     Height h = log₂(n+1) - 1
 */

// Quick reference:
// Balanced: h ≈ log₂(n)
// Skewed: h = n - 1
// Perfect with h levels: n = 2^(h+1) - 1

Space Complexity Deep Dive

// Recursive calls use stack space
// Stack depth = height of tree = h

// Example: Counting nodes recursively
int count(TreeNode root) {
    if (root == null) return 0;
    return 1 + count(root.left) + count(root.right);
}
// Time: O(n) - visit every node
// Space: O(h) - recursion stack

// For balanced tree (h = log n): Space = O(log n)
// For skewed tree (h = n):       Space = O(n)

// BFS space depends on WIDTH, not height
List> levelOrder(TreeNode root) {
    // Queue stores at most one level at a time
    // Max width of perfect tree at level h = 2^h
    // For tree with n nodes, max width ≈ n/2
    // Space: O(n/2) = O(n) worst case
}

// Iterative DFS uses explicit stack
// Space: O(h) same as recursive

Quick visual reference for common tree operations. Print this out or bookmark for quick review!

Tree Types Comparison

Traversal Patterns

BFS Queue Visualization

Stack for DFS Visualization

Recursion Call Stack

Common Tree Formulas

Copy-paste ready code for common operations. Bookmark this section for quick access during practice!

TreeNode Class (Standard)

// Standard TreeNode definition used by LeetCode
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode() {}
    
    TreeNode(int val) { 
        this.val = val; 
    }
    
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

// TreeNode with parent pointer (sometimes needed)
class TreeNodeWithParent {
    int val;
    TreeNodeWithParent left, right, parent;
    
    TreeNodeWithParent(int val) {
        this.val = val;
    }
}

// Generic TreeNode for any data type
class TreeNode {
    T val;
    TreeNode left, right;
    
    TreeNode(T val) {
        this.val = val;
    }
}

Build Tree from Array (LeetCode Format)

// Build tree from level-order array with nulls
// Input: [3, 9, 20, null, null, 15, 7]
// Creates:      3
//              / \
//             9  20
//               /  \
//              15   7

TreeNode buildTree(Integer[] arr) {
    if (arr == null || arr.length == 0 || arr[0] == null) {
        return null;
    }
    
    TreeNode root = new TreeNode(arr[0]);
    Queue queue = new LinkedList<>();
    queue.offer(root);
    int i = 1;

    while (!queue.isEmpty() && i < arr.length) {
        TreeNode current = queue.poll();
        
        // Left child
        if (i < arr.length) {
            if (arr[i] != null) {
                current.left = new TreeNode(arr[i]);
                queue.offer(current.left);
            }
            i++;
        }

        // Right child
        if (i < arr.length) {
            if (arr[i] != null) {
                current.right = new TreeNode(arr[i]);
                queue.offer(current.right);
            }
            i++;
        }
    }
    
    return root;
}

// Usage in main:
Integer[] arr = {3, 9, 20, null, null, 15, 7};
TreeNode root = buildTree(arr);

Print Tree (for Debugging)

// Pretty print tree structure for debugging
void printTree(TreeNode root) {
    printTreeHelper(root, "", true);
}

void printTreeHelper(TreeNode node, String prefix, boolean isLeft) {
    if (node == null) {
        System.out.println(prefix + (isLeft ? "├── " : "└── ") + "null");
        return;
    }
    
    System.out.println(prefix + (isLeft ? "├── " : "└── ") + node.val);
    
    if (node.left != null || node.right != null) {
        printTreeHelper(node.left, prefix + (isLeft ? "│   " : "    "), true);
        printTreeHelper(node.right, prefix + (isLeft ? "│   " : "    "), false);
    }
}

// Simpler version: print level-order with nulls
String treeToString(TreeNode root) {
    if (root == null) return "[]";
    
    StringBuilder sb = new StringBuilder("[");
    Queue queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node == null) {
            sb.append("null, ");
        } else {
            sb.append(node.val).append(", ");
            queue.offer(node.left);
            queue.offer(node.right);
        }
    }

    // Remove trailing nulls for cleaner output
    String result = sb.toString().replaceAll("(, null)+, $", "");
    return result + "]";
}

All Traversals in One Class

class TreeTraversals {
    
    // ========== DFS RECURSIVE ==========
    
    List preorderRecursive(TreeNode root) {
        List result = new ArrayList<>();
        preorderHelper(root, result);
        return result;
    }
    
    void preorderHelper(TreeNode node, List list) {
        if (node == null) return;
        list.add(node.val);           // Process FIRST
        preorderHelper(node.left, list);
        preorderHelper(node.right, list);
    }

    List inorderRecursive(TreeNode root) {
        List result = new ArrayList<>();
        inorderHelper(root, result);
        return result;
    }
    
    void inorderHelper(TreeNode node, List list) {
        if (node == null) return;
        inorderHelper(node.left, list);
        list.add(node.val);           // Process in MIDDLE
        inorderHelper(node.right, list);
    }

    List postorderRecursive(TreeNode root) {
        List result = new ArrayList<>();
        postorderHelper(root, result);
        return result;
    }
    
    void postorderHelper(TreeNode node, List list) {
        if (node == null) return;
        postorderHelper(node.left, list);
        postorderHelper(node.right, list);
        list.add(node.val);           // Process LAST
    }

    // ========== DFS ITERATIVE ==========
    
    List preorderIterative(TreeNode root) {
        List result = new ArrayList<>();
        if (root == null) return result;
        
        Stack stack = new Stack<>();
        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;
    }

    List inorderIterative(TreeNode root) {
        List result = new ArrayList<>();
        Stack stack = new Stack<>();
        TreeNode curr = root;
        
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            result.add(curr.val);
            curr = curr.right;
        }
        return result;
    }

    List postorderIterative(TreeNode root) {
        LinkedList result = new LinkedList<>();
        if (root == null) return result;
        
        Stack stack = new Stack<>();
        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;
    }

    // ========== BFS ==========
    
    List> levelOrder(TreeNode root) {
        List> result = new ArrayList<>();
        if (root == null) return result;
        
        Queue queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            List level = new ArrayList<>();
            
            for (int i = 0; i < size; 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;
    }
}

Common Tree Properties

class TreeProperties {
    
    // Height (max depth)
    int height(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(height(root.left), height(root.right));
    }

    // Count nodes
    int count(TreeNode root) {
        if (root == null) return 0;
        return 1 + count(root.left) + count(root.right);
    }

    // Sum of all values
    int sum(TreeNode root) {
        if (root == null) return 0;
        return root.val + sum(root.left) + sum(root.right);
    }

    // Maximum value
    int max(TreeNode root) {
        if (root == null) return Integer.MIN_VALUE;
        return Math.max(root.val, Math.max(max(root.left), max(root.right)));
    }

    // Minimum value
    int min(TreeNode root) {
        if (root == null) return Integer.MAX_VALUE;
        return Math.min(root.val, Math.min(min(root.left), min(root.right)));
    }

    // Is balanced?
    boolean isBalanced(TreeNode root) {
        return checkHeight(root) != -1;
    }
    
    int checkHeight(TreeNode node) {
        if (node == null) return 0;
        
        int left = checkHeight(node.left);
        if (left == -1) return -1;
        
        int right = checkHeight(node.right);
        if (right == -1) return -1;
        
        if (Math.abs(left - right) > 1) return -1;
        
        return 1 + Math.max(left, right);
    }

    // Is symmetric?
    boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isMirror(root.left, root.right);
    }
    
    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);
    }

    // Diameter (longest path)
    int diameter = 0;
    
    int diameterOfBinaryTree(TreeNode root) {
        diameter = 0;
        depth(root);
        return diameter;
    }
    
    int depth(TreeNode node) {
        if (node == null) return 0;
        int left = depth(node.left);
        int right = depth(node.right);
        diameter = Math.max(diameter, left + right);
        return 1 + Math.max(left, right);
    }
}

Complete Solution Template

import java.util.*;

class Solution {
    // Your tree algorithm here
}

    public static void main(String[] args) {
        // Build test tree
        //       1
        //      / \
        //     2   3
        //    / \
        //   4   5
        
        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);

        Solution sol = new Solution();
        
        // Test your solution
        System.out.println("Testing...");
        
        // Example: test height
        // System.out.println("Height: " + sol.maxDepth(root));
        
        // Example: test traversal
        // System.out.println("Inorder: " + sol.inorderTraversal(root));
    }

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