Tree Interview Problems — Stack Overflow on 50k-Node Trees

package io.thecodeforge.trees;

/**
 * io.thecodeforge: Efficiently calculating the maximum depth of a Binary Tree.
 * Pattern: Recursive DFS (Post-order)
 */
public class DepthCalculator {
    public int maxDepth(TreeNode root) {
        // Base Case: An empty tree has depth 0
        if (root == null) {
            return 0;
        }

        // Recursive Step: Gather information from children
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);

        // Combine Step: Current depth is max of children + 1 (itself)
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

package io.thecodeforge.trees;

import java.util.*;

public class LevelExplorer {
    /**
     * io.thecodeforge: Standard Level-Order Traversal implementation.
     */
    public List<List<Integer>> levelOrder(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> 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;
    }
}

package io.thecodeforge.trees;

public class TreeComparison {
    // Pattern: Two-pointer recursion — compare two nodes simultaneously
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        if (p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

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

    private boolean isMirror(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        return (left.val == right.val)
            && isMirror(left.left, right.right)
            && isMirror(left.right, right.left);
    }
}

package io.thecodeforge.trees;

public class BottomUpAggregator {
    private int diameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return diameter;
    }

    private int height(TreeNode node) {
        if (node == null) return 0;
        int leftHeight = height(node.left);
        int rightHeight = height(node.right);
        // Update diameter: longest path through this node
        diameter = Math.max(diameter, leftHeight + rightHeight);
        // Return height of this node to parent
        return Math.max(leftHeight, rightHeight) + 1;
    }

    // Maximum Path Sum variant (LeetCode 124)
    private int maxPathSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxPathSum;
    }

    private int maxGain(TreeNode node) {
        if (node == null) return 0;
        int leftGain = Math.max(0, maxGain(node.left));  // ignore negative gains
        int rightGain = Math.max(0, maxGain(node.right));
        int currentMax = node.val + leftGain + rightGain;
        maxPathSum = Math.max(maxPathSum, currentMax);
        // Return the maximum sum if you go down one path from this node
        return node.val + Math.max(leftGain, rightGain);
    }
}

package io.thecodeforge.trees;

import java.util.*;

public class TreeSerializer {
    private static final String NULL_MARKER = "null";
    private static final String DELIMITER = ",";

    // Serialize using pre-order traversal
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serializeHelper(root, sb);
        return sb.toString();
    }

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

    // Deserialize using a queue from the serialized array
    public TreeNode deserialize(String data) {
        String[] parts = data.split(DELIMITER);
        Queue<String> queue = new LinkedList<>(Arrays.asList(parts));
        return deserializeHelper(queue);
    }

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

package io.thecodeforge.trees;

import java.util.*;

public class BSTValidator {
    // Recursive range-based validation
    public boolean isValidBST(TreeNode root) {
        return validate(root, null, null);
    }

    private boolean validate(TreeNode node, Integer low, Integer high) {
        if (node == null) return true;
        if ((low != null && node.val <= low) || (high != null && node.val >= high)) return false;
        return validate(node.left, low, node.val) && validate(node.right, node.val, high);
    }

    // Iterative in-order validation (uses stack) – early exit
    public boolean isValidBSTIterative(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        Integer prev = null;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            if (prev != null && curr.val <= prev) return false;
            prev = curr.val;
            curr = curr.right;
        }
        return true;
    }

    // Kth Smallest Element in BST
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        int count = 0;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            count++;
            if (count == k) return curr.val;
            curr = curr.right;
        }
        return -1;
    }
}