CMD Guide
Home › DSA

Trees

Step 11 in the DSA path · 14 concepts · 71 problems

0 / 85 complete

📘 Learn Trees from zero

The Tree DFS pattern walks a binary tree recursively (root → left subtree → right subtree), letting each node compute its answer from the answers its children return back up the call stack. The trigger: any problem asking about depth, height, path sums, or aggregating information along root-to-leaf paths — when a node's result depends on what lies below it, do post-order DFS and combine child results. Canonical example: Maximum Depth of a Binary Tree, where depth(node) = 1 + max(depth(left), depth(right)) and an empty child contributes depth 0.

✨ Added by the guide to build intuition — not from the source course.

🏗️ Visual walkthrough — trace it step by step

Step 1 — The tree and the recurrence
          3            <- root
         / \
        9   20
           /  \
          15   7

We compute maxDepth(root). The rule is depth(node) = 1 + max(depth(node.left), depth(node.right)), and depth(null) = 0. DFS dives to the bottom first, then each node folds its children's depths upward — this is safe because a node's height is fully determined by its subtrees, which are resolved before the node returns.

Step 2 — Descend left to leaf 9
          3
         / \
      [9]   20         call stack: 3 -> 9
           /  \
          15   7

At 9: left=null, right=null

We recurse into 3.left = 9. Node 9 has no children, so it calls depth(null) on both sides. Reaching a leaf is the base-case frontier; the recursion must bottom out here so values can start flowing back up.

Step 3 — Leaf 9 returns its depth
          3
         / \
      (9)=1  20        9 returns 1
           /  \
          15   7

depth(9) = 1 + max(depth(null), depth(null))
        = 1 + max(0, 0) = 1

Both null children return 0, so node 9 returns 1 + max(0,0) = 1. This is correct: a single-node subtree has depth 1. Node 9's frame pops off the stack; control returns to node 3, which now holds leftDepth = 1.

Step 4 — Descend right into 20, then to leaf 15
          3
         / \
      (9)=1 [20]        stack: 3 -> 20 -> 15
           /  \
        (15)=1  7

depth(15) = 1 + max(0, 0) = 1   -> 15 returns 1

Now node 3 explores its right child 20, which stays on the stack (shown as [20]) while we recurse left-first into 20.left = 15. Leaf 15 has two null children, so it returns 1 + max(0,0) = 1 and pops. We always finish the left subtree completely before touching the right — that ordering is what makes the depths we combine final, never partial. Node 20 now holds leftDepth = 1 and still awaits its right child 7.

Step 5 — Leaf 7 returns, node 20 folds its children
          3
         / \
      (9)=1 (20)=2      20 returns 2
           /  \
      (15)=1 (7)=1

depth(20) = 1 + max(depth(15), depth(7))
         = 1 + max(1, 1) = 2

Node 20 recurses into its right child 7, another leaf, which returns 1. Node 20 now has both child results in hand (leftDepth = 1, rightDepth = 1) and returns 1 + max(1,1) = 2. It is safe to combine here because 20 only resumes after both 15 and 7 have fully popped — their returned depths can never change.

Step 6 — Root 3 combines both subtrees
          3            ROOT resolves
         / \
      (9)=1 (20)=2
           /  \
      (15)=1 (7)=1

depth(3) = 1 + max(depth(9), depth(20))
        = 1 + max(1, 2) = 3

The root finally has leftDepth = 1 (from 9) and rightDepth = 2 (from 20). It returns 1 + max(1,2) = 3. The deeper right branch wins via max, so the answer counts the longest root-to-leaf chain 3 → 20 → 15.

Step 7 — Result and complexity
maxDepth(root) = 3

Longest path: 3 -> 20 -> 15  (3 nodes)
              3 -> 20 -> 7   (also 3, tie)

Visited each node exactly once:
  3, 9, 20, 15, 7  -> 5 nodes

Final answer: 3. Every node was visited once, so time is O(n); space is O(h) for the recursion stack (h = tree height, worst case O(n) for a skewed tree). This same post-order fold generalizes directly to Tree Diameter and Path Sum — only the combine step changes.

🎯 Guided practice

  1. Easy — Maximum Depth (Height) of a Binary Tree. Return the number of nodes on the longest root-to-leaf path (LeetCode's convention: empty tree → 0, single node → 1 — this counts nodes, not edges, so it is one greater than the formal edge-based height).

    Step 1 — frame it as bottom-up DFS: a node's depth is "1 (for itself) plus the deeper of its two children." The answer at a node depends only on its subtrees, which is the signal for post-order DFS.

    Step 2 — base case: if node is None, return 0.

    Step 3 — recurse and combine: return 1 + max(maxDepth(node.left), maxDepth(node.right)).

    Step 4 — trace a root with only a left child: maxDepth(leftChild) = 1 + max(0, 0) = 1; the missing right child returns 0; so maxDepth(root) = 1 + max(1, 0) = 2. Correct.

    Complexity: O(n) time (each node visited once), O(h) stack space. This is the canonical "post-order DFS returns a value" template — Tree Diameter, balanced-tree check, and many "compute something over every subtree" problems reuse it verbatim, often returning the height while updating a global best on the side.

  2. Medium — Validate Binary Search Tree. Return true only if for every node, all values in its left subtree are strictly smaller and all values in its right subtree are strictly larger.

    Step 1 — spot the trap: a local check (node.left.val < node.val < node.right.val) is wrong — a node deep in a subtree can still violate a distant ancestor. Each node must obey a range inherited from above.

    Step 2 — carry bounds: define valid(node, low, high); the root starts with (-inf, +inf). (Equivalently, an in-order traversal must produce strictly increasing values — a clean alternative worth mentioning.)

    Step 3 — check and narrow: if node is None return true. If not (low < node.val < high) return false. Recurse left with (low, node.val) and right with (node.val, high) — going left tightens the upper bound, going right tightens the lower bound.

    Step 4 — trace root 5, right child 7, and 7's left child 3. Root sees (-inf, +inf): 5 passes. Right subtree inherits (5, +inf): 7 passes. Node 3 inherits (5, 7) and fails 5 < 3 → returns false. A parent-only check would wrongly accept it, since 3 < 7 locally holds.

    Complexity: O(n) time, O(h) space. The lesson — thread constraints down the recursion — generalizes to many "is this structure valid" tree problems where validity is a global, not local, property.

✨ Added by the guide — work these before the full problem set.

Lessons in this topic

🧠 Review & recall

Active recall is what moves a topic into long-term memory. Flip each card before revealing, then test yourself — your results are saved on this device.

Flashcard
What signal tells you to reach for post-order (bottom-up) Tree DFS, and what is the canonical recurrence?
tap to reveal →
Use post-order DFS when a node's answer depends on what lies below it — questions about depth, height, path sums, or aggregating along root-to-leaf paths. Canonical example is Maximum Depth: depth(node) = 1 + max(depth(left), depth(right)), with depth(null) = 0.
💡 'Children answer first, parent folds them up' — dive to the leaves, then combine on the way back.
Flashcard
What order does each DFS traversal visit nodes, and what is each one's classic use?
tap to reveal →
Inorder = Left -> Root -> Right (returns BST nodes in ascending sorted order). Preorder = Root -> Left -> Right (cloning trees / prefix expressions). Postorder = Left -> Right -> Root (deleting trees / postfix expressions).
💡 Position of 'Root' names it: pre=first, in=middle, post=last.
Flashcard
What is the time and space complexity of a recursive tree traversal, and why does space vary?
tap to reveal →
Time is O(n) since every node is visited once. Space is O(h) for the recursion stack, where h is tree height — O(log n) for a balanced tree but O(n) worst case for a skewed (linked-list-like) tree.
💡 Time follows nodes (n); space follows depth (h).
Flashcard
Why does a local parent-child comparison fail to validate a BST, and what is the correct method?
tap to reveal →
A local check (left < node < right) misses violations from distant ancestors — a node deep in a subtree can still break an ancestor's bound. Correct approach: carry an inherited range valid(node, low, high) starting (-inf, +inf); going left tightens the upper bound to node.val, going right tightens the lower bound. (Equivalently, an inorder traversal must be strictly increasing.)
💡 Every node lives inside a range it inherits from above — not just from its parent.
Flashcard
How does the BST property let you find the Lowest Common Ancestor without a full tree search?
tap to reveal →
Walk from the root: if both p and q are less than the current node, go left; if both are greater, go right; the moment they diverge (one on each side, or one equals the node), that node is the LCA. Runs in O(h) time iteratively.
💡 LCA = the first node where p and q split paths (the 'fork in the road').
Flashcard
How does Path with Maximum Sum (hard) reuse the diameter/path-sum DFS, and what is the key twist?
tap to reveal →
It's a post-order DFS like Tree Diameter. At each node, clamp negative child sums to 0 (ignore negative paths), compute a local 'through' sum = leftMax + rightMax + node.val to update a global maximum, but return only max(leftMax, rightMax) + node.val upward (a path can't fork twice). O(n) time, O(n) worst-case stack space.
💡 Update global with both sides; return only one side up. Clamp negatives to 0.
Q1. Which traversal of a Binary Search Tree yields the node values in ascending sorted order?
Q2. For Maximum Depth of a Binary Tree, what does maxDepth return for a root that has only a left child which is a single leaf?
Q3. What is the worst-case space complexity of recursively traversing a binary tree, and when does it occur?
Q4. In a BST, both query nodes p and q have values greater than the current node during an LCA search. What should the algorithm do?
Q5. In Path with Maximum Sum, why is each child's returned subtree sum clamped with max(childSum, 0) before being used?