Binary Tree Recursion — Why 15K Nodes Crashed Production

// A self-contained binary tree built from scratch.
// We're building a small family tree to make the analogy concrete.

public class BinaryTreeNode {

    // Each node holds a name (the data) and references to its two children.
    String name;
    BinaryTreeNode leftChild;
    BinaryTreeNode rightChild;

    // Constructor — when a node is born, it has no children yet.
    public BinaryTreeNode(String name) {
        this.name = name;
        this.leftChild = null;  // No left child yet
        this.rightChild = null; // No right child yet
    }

    public static void main(String[] args) {
        // Build the root — the top of our family tree
        BinaryTreeNode grandparent = new BinaryTreeNode("Alice");

        // Alice's two children
        grandparent.leftChild = new BinaryTreeNode("Bob");
        grandparent.rightChild = new BinaryTreeNode("Carol");

        // Bob's two children (grandchildren of Alice)
        grandparent.leftChild.leftChild = new BinaryTreeNode("Dave");
        grandparent.leftChild.rightChild = new BinaryTreeNode("Eve");

        // Carol has only one child (that's still valid — at MOST two, not exactly two)
        grandparent.rightChild.leftChild = new BinaryTreeNode("Frank");

        // Let's inspect the structure manually
        System.out.println("Root: " + grandparent.name);
        System.out.println("Root's left child: " + grandparent.leftChild.name);
        System.out.println("Root's right child: " + grandparent.rightChild.name);
        System.out.println("Bob's left child: " + grandparent.leftChild.leftChild.name);
        System.out.println("Bob's right child: " + grandparent.leftChild.rightChild.name);
        System.out.println("Carol's left child: " + grandparent.rightChild.leftChild.name);
        System.out.println("Carol's right child: " + grandparent.rightChild.rightChild); // null!

        // Calculate height manually to understand the concept
        System.out.println("\nTree height: " + calculateHeight(grandparent));
        System.out.println("Total nodes: " + countNodes(grandparent));
    }

    // Height = longest path from this node down to a leaf
    // Base case: a null node has height -1; a leaf has height 0
    static int calculateHeight(BinaryTreeNode node) {
        if (node == null) return -1; // went past a leaf
        int leftHeight = calculateHeight(node.leftChild);
        int rightHeight = calculateHeight(node.rightChild);
        // Take the taller side and add 1 for the current node itself
        return 1 + Math.max(leftHeight, rightHeight);
    }

    // Count every node in the tree using recursion
    static int countNodes(BinaryTreeNode node) {
        if (node == null) return 0;
        // This node (1) + everything on the left + everything on the right
        return 1 + countNodes(node.leftChild) + countNodes(node.rightChild);
    }
}

import java.util.LinkedList;
import java.util.Queue;

public class TreeTraversals {

    static class Node {
        int value;
        Node left, right;

        Node(int value) {
            this.value = value;
        }
    }

    // IN-ORDER: Left → Current → Right
    // Use case: print BST nodes in sorted order
    static void inOrder(Node node) {
        if (node == null) return; // Base case — nothing to visit
        inOrder(node.left);           // Go all the way left first
        System.out.print(node.value + " "); // Visit this node
        inOrder(node.right);          // Then explore the right
    }

    // PRE-ORDER: Current → Left → Right
    // Use case: serialise/clone a tree, since parent is always saved before children
    static void preOrder(Node node) {
        if (node == null) return;
        System.out.print(node.value + " "); // Visit this node FIRST
        preOrder(node.left);
        preOrder(node.right);
    }

    // POST-ORDER: Left → Right → Current
    // Use case: delete a tree safely, or evaluate an expression tree
    static void postOrder(Node node) {
        if (node == null) return;
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.value + " "); // Visit this node LAST
    }

    // BREADTH-FIRST (Level-order): visit level by level using a Queue
    // Use case: find shortest path, print tree level by level
    static void breadthFirst(Node root) {
        if (root == null) return;

        Queue<Node> queue = new LinkedList<>();
        queue.offer(root); // Start with the root in the queue

        while (!queue.isEmpty()) {
            Node current = queue.poll(); // Take the front node
            System.out.print(current.value + " ");

            // Enqueue children so they're visited in the next round
            if (current.left != null) queue.offer(current.left);
            if (current.right != null) queue.offer(current.right);
        }
    }

    public static void main(String[] args) {
        /*
         * Building this tree:
         *
         *         10
         *        /  \
         *       5    15
         *      / \     \
         *     3   7    20
         */
        Node root = new Node(10);
        root.left = new Node(5);
        root.right = new Node(15);
        root.left.left = new Node(3);
        root.left.right = new Node(7);
        root.right.right = new Node(20);

        System.out.print("In-Order:      ");
        inOrder(root);       // Sorted order for a BST
        System.out.println();

        System.out.print("Pre-Order:     ");
        preOrder(root);      // Root first — good for serialisation
        System.out.println();

        System.out.print("Post-Order:    ");
        postOrder(root);     // Root last — good for deletion
        System.out.println();

        System.out.print("Breadth-First: ");
        breadthFirst(root);  // Level by level
        System.out.println();
    }
}

import java.util.Stack;

public class IterativeTraversals {

    static class Node {
        int value;
        Node left, right;
        Node(int v) { this.value = v; }
    }

    // Iterative In-Order: Left → Current → Right
    static void iterativeInOrder(Node root) {
        Stack<Node> stack = new Stack<>();
        Node current = root;
        while (current != null || !stack.isEmpty()) {
            // Push all left nodes
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            // Pop and visit
            current = stack.pop();
            System.out.print(current.value + " ");
            // Go right
            current = current.right;
        }
    }

    // Iterative Pre-Order: Current → Left → Right
    static void iterativePreOrder(Node root) {
        if (root == null) return;
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node current = stack.pop();
            System.out.print(current.value + " ");
            // Push right first so left is processed next
            if (current.right != null) stack.push(current.right);
            if (current.left != null) stack.push(current.left);
        }
    }

    // Iterative Post-Order using two stacks
    static void iterativePostOrder(Node root) {
        if (root == null) return;
        Stack<Node> stack1 = new Stack<>();
        Stack<Node> stack2 = new Stack<>();
        stack1.push(root);
        while (!stack1.isEmpty()) {
            Node current = stack1.pop();
            stack2.push(current);
            if (current.left != null) stack1.push(current.left);
            if (current.right != null) stack1.push(current.right);
        }
        while (!stack2.isEmpty()) {
            System.out.print(stack2.pop().value + " ");
        }
    }

    public static void main(String[] args) {
        /*
         * Tree:
         *       1
         *      / \
         *     2   3
         *    / \
         *   4   5
         */
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);

        System.out.print("Iterative In-Order:   ");
        iterativeInOrder(root);   // 4 2 5 1 3
        System.out.println();
        System.out.print("Iterative Pre-Order:  ");
        iterativePreOrder(root);  // 1 2 4 5 3
        System.out.println();
        System.out.print("Iterative Post-Order: ");
        iterativePostOrder(root); // 4 5 2 3 1
        System.out.println();
    }
}

public class BinaryTreeProblems {

    static class Node {
        int value;
        Node left, right;

        Node(int value) { this.value = value; }
    }

    // PROBLEM 1: Does a target value exist anywhere in the tree?
    // Uses depth-first search — returns true the moment we find it.
    static boolean search(Node node, int target) {
        if (node == null) return false;       // Fell off the tree — not found
        if (node.value == target) return true; // Found it!

        // Check left subtree first; if not there, check right subtree
        return search(node.left, target) || search(node.right, target);
    }

    // PROBLEM 2: Lowest Common Ancestor
    // Returns the deepest node that is an ancestor of BOTH firstTarget and secondTarget.
    // Real use: Git merge-base, network routing, UI component trees
    static Node lowestCommonAncestor(Node node, int firstTarget, int secondTarget) {
        // Base case: gone past a leaf, or we've landed ON one of the targets
        if (node == null) return null;
        if (node.value == firstTarget || node.value == secondTarget) return node;

        // Recurse into both subtrees
        Node leftResult = lowestCommonAncestor(node.left, firstTarget, secondTarget);
        Node rightResult = lowestCommonAncestor(node.right, firstTarget, secondTarget);

        // If both sides found a target, the current node is the LCA
        if (leftResult != null && rightResult != null) return node;

        // Otherwise bubble up whichever side found something (or null if neither did)
        return (leftResult != null) ? leftResult : rightResult;
    }

    // PROBLEM 3: Check if the tree is symmetric (mirrors itself around the root)
    // Used in image processing, parsing balanced expressions, UI layout validation
    static boolean isSymmetric(Node root) {
        return isMirror(root, root);
    }

    static boolean isMirror(Node leftNode, Node rightNode) {
        if (leftNode == null && rightNode == null) return true;  // Both absent — symmetric
        if (leftNode == null || rightNode == null) return false; // One absent — not symmetric
        if (leftNode.value != rightNode.value) return false;     // Different values — not symmetric

        // The outside pair and inside pair must both be mirrors
        return isMirror(leftNode.left, rightNode.right)
            && isMirror(leftNode.right, rightNode.left);
    }

    public static void main(String[] args) {
        /*
         * Tree for LCA and search problems:
         *
         *           1
         *          / \
         *         2   3
         *        / \   \
         *       4   5   6
         */
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.right = new Node(6);

        System.out.println("--- Search ---");
        System.out.println("Search for 5: " + search(root, 5)); // true
        System.out.println("Search for 9: " + search(root, 9)); // false

        System.out.println("\n--- Lowest Common Ancestor ---");
        Node lca1 = lowestCommonAncestor(root, 4, 5);
        System.out.println("LCA of 4 and 5: " + lca1.value); // 2 (both under node 2)

        Node lca2 = lowestCommonAncestor(root, 4, 6);
        System.out.println("LCA of 4 and 6: " + lca2.value); // 1 (root — they're in different subtrees)

        Node lca3 = lowestCommonAncestor(root, 2, 5);
        System.out.println("LCA of 2 and 5: " + lca3.value); // 2 (node IS its own ancestor)

        System.out.println("\n--- Symmetry Check ---");
        /*
         * Symmetric tree:
         *       1
         *      / \
         *     2   2
         *    / \ / \
         *   3  4 4  3
         */
        Node symmetricRoot = new Node(1);
        symmetricRoot.left = new Node(2);
        symmetricRoot.right = new Node(2);
        symmetricRoot.left.left = new Node(3);
        symmetricRoot.left.right = new Node(4);
        symmetricRoot.right.left = new Node(4);
        symmetricRoot.right.right = new Node(3);

        System.out.println("Is original tree symmetric? " + isSymmetric(root));          // false
        System.out.println("Is symmetric tree symmetric? " + isSymmetric(symmetricRoot)); // true
    }
}