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.

🌳
Core vocabulary
Terms you'll see in every tree problem
  • 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

10 root 5 left child 15 right child 2 leaf 7 leaf 20 leaf siblings: 2 & 7 Height = 2 · Depth of node 7 = 2
Internal node Leaf node Root

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.

tree_node.py The building block for every tree problem
Output
Root: 10 Left child: 5 Right child: 15 Leaves: 2, 7, 20
Interview pattern:
Almost every tree problem on LeetCode uses this exact 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]

10 5 15 2 7 20
Inorder: 2→5→7→10→15→20
Preorder: 10→5→2→7→15→20
Postorder: 2→7→5→20→15→10
Level-order: 10→5→15→2→7→20
traversals.py All four traversals — DFS recursive + BFS iterative
Output
Inorder: [2, 5, 7, 10, 15, 20] Preorder: [10, 5, 2, 7, 15, 20] Postorder: [2, 7, 5, 20, 15, 10] Level-order: [[10], [5, 15], [2, 7, 20]]
Memory aid:
The name tells you where the root goes. Inorder = root in the middle. Preorder = root first. Postorder = root last. Level-order is the odd one out — it uses a queue (BFS) instead of recursion (DFS).

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.

🧭
When to use which
DFS for paths, BFS for levels
  • 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)
Interview tip:
If the problem mentions "level", "layer", "distance from root", or "shortest" — start with BFS. If it mentions "path", "subtree", "depth", or "height" — start with DFS. Most tree problems use DFS because recursion maps naturally to the tree structure.

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.

max_depth.py O(n) time, O(h) space — h is tree height
Output
Max depth: 3 Empty tree: 0 Single node: 1

How it works

  1. Base case: If root is None, depth is 0.
  2. Recurse: Ask left and right subtrees for their depths.
  3. Combine: Take the max of both, add 1 for the current node.
Think recursively:
"The depth of a tree is 1 + the depth of its deepest subtree." This one-line insight is the entire solution. Every tree problem follows this pattern: solve for children, combine at 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."

invert_tree.py O(n) time, O(h) space
Output
Before: [4, 2, 7, 1, 3, 6, 9] After: [4, 7, 2, 9, 6, 3, 1]

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.

same_tree.py O(n) time, O(h) space
Output
Same? True Same? False Same? False

Three base cases — the pattern for all tree comparisons

  1. Both None: Two empty trees are identical → True
  2. One None: One tree ended early → False
  3. 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

Path Sum (LeetCode 112)
Your task:

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.

Define 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

Question 1 of 5
What is the maximum number of children a node can have in a binary tree?
Question 2 of 5
Which traversal visits nodes in sorted order for a Binary Search Tree?
Question 3 of 5
What data structure does level-order (BFS) traversal use?
Question 4 of 5
What does max_depth return for an empty tree (root is None)?
Question 5 of 5
In invert_tree, what happens to the left and right children of every node?
0
/5
Great work! You understand binary trees.
Africa & India's Best AI Academy
🤖 AI-first 🎓 Placement Assistance

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 →