Tree Terminology
Before writing any code, you need to speak the language of trees. Every interview problem description uses these terms, and misunderstanding one can lead you down the wrong path entirely.
- Root — The topmost node. It has no parent.
- Node — Each element in a tree, holding a value and references to children.
- Leaf — A node with no children (both left and right are
None). - Parent / Child — A node that points to another is the parent; the pointed-to node is the child.
- Sibling — Nodes that share the same parent.
- Depth — The number of edges from the root to a node. The root has depth 0.
- Height — The number of edges on the longest path from a node down to a leaf. A leaf has height 0.
- Subtree — Any node and all its descendants form a subtree.
Labeled Binary Tree
Binary Tree & TreeNode Class
A binary tree is a tree where each node has at most 2 children — called left and right. This constraint is what makes binary trees special: every recursive problem splits into exactly two subproblems.
TreeNode class. The val + left + right structure is universal. You won't need to define it in interviews — it's given — but understanding it deeply is essential.
Tree Traversals
Traversals are the core of tree problems. There are four ways to visit every node, and each has a distinct use case. Master these four and you can solve 80% of tree interview questions.
The Four Traversals
- Inorder (Left → Root → Right) — Gives sorted order for BSTs.
- Preorder (Root → Left → Right) — Used to serialize or copy trees.
- Postorder (Left → Right → Root) — Used to delete trees or compute from leaves up.
- Level-order (BFS) — Process level by level using a queue.
Traversal Order on Sample Tree [10, 5, 15, 2, 7, null, 20]
DFS vs BFS on Trees
Both DFS and BFS visit every node, but they explore in fundamentally different orders. Choosing the right one can simplify your solution dramatically.
- DFS (Depth-First Search) — Goes deep before going wide. Use for path problems, subtree calculations, and anything where you need to process all descendants before moving to siblings. Implemented with recursion or an explicit stack.
- BFS (Breadth-First Search) — Goes wide before going deep. Use for level-order processing, shortest path in unweighted trees, and "find nearest" problems. Implemented with a queue.
Quick decision guide
- "Find the maximum depth" → DFS (recurse to leaves, bubble up)
- "Find all root-to-leaf paths" → DFS (track path as you recurse)
- "Print level by level" → BFS (queue processes one level at a time)
- "Find the leftmost node at the deepest level" → BFS (last level, first node)
- "Check if tree is symmetric" → Either (DFS with mirrored recursion or BFS with paired comparison)
Problem: Maximum Depth
Given the root of a binary tree, return its maximum depth — the number of nodes along the longest path from root to leaf. This is LeetCode 104 and one of the first tree problems every interviewer asks.
How it works
- Base case: If
rootisNone, depth is 0. - Recurse: Ask left and right subtrees for their depths.
- Combine: Take the max of both, add 1 for the current node.
Problem: Invert Binary Tree
Given the root of a binary tree, invert it — swap every left and right child. This is LeetCode 226, famously the problem that inspired the tweet "Google: 90% of our engineers use the software you wrote, but you can't invert a binary tree on a whiteboard so goodbye."
The elegance is in the single line: root.left, root.right = invert_tree(root.right), invert_tree(root.left). Python's simultaneous assignment means we don't need a temporary variable. The recursion inverts both subtrees, then swaps them.
Problem: Same Tree
Given the roots of two binary trees, determine if they are structurally identical with the same node values. This is LeetCode 100. It's a clean exercise in understanding recursive base cases.
Three base cases — the pattern for all tree comparisons
- Both None: Two empty trees are identical →
True - One None: One tree ended early →
False - Values differ: Same structure but different data →
False
If all three checks pass, recurse on both children. This three-check pattern appears in symmetric tree, subtree check, and mirror tree problems too.
Try It Yourself
Find the Maximum Depth of a Binary Tree
Implement max_depth(root) that returns the maximum depth. The TreeNode class is provided. Build a test tree and verify your solution.
Challenge
Given the root of a binary tree and an integer targetSum, return True if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.
Example: For a tree [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1] and targetSum = 22, the path 5 → 4 → 11 → 2 sums to 22, so return True.
Approach: DFS, subtracting the current node's value from the target at each step. At a leaf, check if the remaining target is 0.
has_path_sum(root, target). Base case: if root is None, return False. If it's a leaf (no left or right), return root.val == target. Otherwise, recurse: has_path_sum(root.left, target - root.val) or has_path_sum(root.right, target - root.val). The subtraction carries the running sum without an extra parameter.Quiz
max_depth return for an empty tree (root is None)?invert_tree, what happens to the left and right children of every node?You've learned to think recursively about trees.
Now grow your career the same way — one strong foundation at a time.
Join the Best AI Programs — three 5-month courses, fully online, with placement assistance. Week 1 is free.
Explore our AI-era courses →