Last Minute Notes
  • Github
  • Docs
  • Learn
    @sayanstwt
Lessons
0/15 done
  • Tree BFS
  • Tree DFS
  • Two Heaps
  • Top K Elements
  • K-way Merge
  • Trie
Learn/Data Structures & Algorithms/Trees & Heaps

Tree DFS

7 min Beginner 8 steps

Recurse down paths and carry state back up.

Target
22
Leaves
4
Paths found
0
548111347251find every root-to-leaf path that sums to 22
current visited done
In this lessonStep 1 of 8
  1. The problem
  2. Three orders
  3. Stack
  4. Pass down
  5. Return up
  6. Global best
  7. BFS or DFS
  8. Recap
Step 1 / 8problem

Answers that live on paths

Find every root-to-leaf path in this tree that sums to 22.

Levels do not help here. You need to follow one path all the way down, remember it, then back up and try the next.

Key idea

Path sums, heights, diameters, validity, all routes: anything about paths or subtrees wants DFS.

←→ step·R replay·Space pause

You'll learn

  • Pick preorder, inorder or postorder from what each node needs
  • Pass state down as parameters and backtrack
  • Return state up from children (postorder)
  • Keep a global best when the answer bends through a node
  • Choose between BFS and DFS by tree shape
Read the full notesTrees, Graphs and Search, 3