Binary Trees

A binary tree is a recursive structure: each node has at most a left child and a right child, and each child is itself the root of another binary tree. Most binary-tree algorithms are just careful answers to: what do I need from the left subtree, the right subtree, and the current node?

The Recursive Shape

A null node is the base case. A non-null node combines answers from left and right. Maximum depth is one plus the larger child depth. Diameter is the best path through a node or inside one child.

Scenario: Comment Thread Shape

A threaded discussion can become tree-shaped. Moderation tools may need the deepest reply chain, total visible replies, or level-order display. A skewed thread behaves like a linked list and can create recursion-depth risk.

Same Pattern in Java, Python, and JavaScript

Maximum depth is the cleanest binary-tree recursion. The same structure appears in many harder problems.

class TreeNode { int value; TreeNode left; TreeNode right; }

class MaxDepthTree {
    static int maxDepth(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
    }
}

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

• Return the maximum root-to-leaf depth of a binary tree.
• Return the length of the longest path between any two nodes.
• Return whether two binary trees have identical structure and values.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Solved modelInterview Question Solutions

class TreeNode { int value; TreeNode left; TreeNode right; }

class MaxDepthTree {
    static int maxDepth(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
    }
}

class Node { Node left, right; }
class Diameter { int best = 0; int diameter(Node root) { height(root); return best; } int height(Node node) { if (node == null) return 0; int l = height(node.left), r = height(node.right); best = Math.max(best, l + r); return 1 + Math.max(l, r); } }

class Node { int val; Node left, right; }
class SameTree { static boolean same(Node a, Node b) { if (a == null || b == null) return a == b; return a.val == b.val && same(a.left, b.left) && same(a.right, b.right); } }

Solved modelWorked Interview Answer

Compute the maximum depth of a binary tree. Return one fact from each subtree: its depth. The current node contributes one level above the deeper child.

class TreeNode { int value; TreeNode left; TreeNode right; }

class MaxDepthTree {
    static int maxDepth(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
    }
}

Hands-on drillTry It Yourself

Failure patternsCommon Mistakes to Avoid

• Forgetting null as base case.
• Assuming balanced height.
• Confusing depth with diameter.
• Recomputing heights repeatedly in diameter.
• Ignoring recursion stack space.

Execution guardrailQuick-Start Checklist

• Define what each recursive call returns.
• Handle null node.
• Combine left and right results.
• Track global answer when needed.
• State O(n) time.
• State O(height) stack space.

Recall drillKnowledge Check

VocabularyKey Terms

Next practiceFurther Reading

• Practice max depth, diameter, same tree, invert tree, and balanced tree.
• Review recursive postorder aggregation.
• Compare recursive and iterative DFS for deep trees.