Knowledge Guide
Home › DSA

Trees

Step 11 in the DSA path · 23 concepts · 72 problems

0 / 95 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