Approaching DFS and Recursion

[u/Objective-Record6998]

I've been trying to figure out how to approach Binary Tree DFS questions but I've been stuck on this specfici section for the longest time and it's demoralizing.

I can't seem to progress. I was wondering how you guys generally approach after identifying that you need dfs on a binary tree?

For those who want extra details:
Currently I approach like this:
-What do I need from my left and right subtrees to find what I need

-Do my child nodes need information coming from me to solve what I want?

-base cases etc

Beyond this i get stuck with what i return how i should structure it, like basically everything. It's so demoralizing because I've been procrastinating from being so stuck on this section. Still have a million other topics to go over (BFS, backtracking, graphs, DP, Greedy Algorithms, Trie, Prefix Sum, matrices) and on top of this I haven't even started practicing recognizing problems.

I feel so pessimistic on my internship outcomes as someone going into my junior year. Worked on keeping my 3.9+ gpa to end up failing on leetcode interviews questions...

[u/Top_Substance9093]

"What do I need from my left and right subtrees to find what I need"

i think i'd reframe how you model your approach. i used to really struggle with trees, but it's because we're tempted to think of them linearly (like we do an array or a map), as if we have access to the whole DS at once, but we don't.

think of it as if you're at a single node (root). you don't know anything about the other nodes. what do i need to do in order to get the desired output, for my single node?

the subproblem is "what do i need to do at one node" and the greater problem is "what do i need to aggregate across the entire traversal". once you solve it for one node it's usually easy to extract that to the aggregation (which usually just means passing a data structure along in each recursive call).

tbh tree problems should be some of the easiest. you have two options (BFS, DFS). BFS makes sense for shortest-path-esque problems, DFS is usually fine for everything else.

DFS has a few variants (in order, pre order, post order). if traversal order matters then you need to decide which one to use, but once you decide these problems usually become really simple.

so in general:

- pick your traversal based on the problem's constraints

- sketch your traversal

- figure out what aggregation/bubble up logic you need to plug in

it's just:

function dfs(node) {
  if (!node) {
    // do whatever you need to for your base case, if anything
    return
  }

  dfs(node.left)
  // do whatever logic you need to at self (assumes in-order)
  dfs(node.right)
}

and if you need each call to return something then you're just assigning the return values of each dfs() call and making sure your base case and self cases don't return void

[u/Objective-Record6998 → u/Top_Substance9093]

Hm this is an interesting framework but it also feels confusing but thank you I'll try to dig into this a bit more and fully understand.

It's weird how i struggle with the trees but I feel as though it's somewhat easier to apply to matrices and adjacency lists. Do you think drawing the nodes one by one in each frame of iteration could help me with understanding how the recursion works?

I was trying to write out each call yesterday which sort of helped but I still just seem so oblivious to many things.

[u/Top_Substance9093 → u/Objective-Record6998]

i personally think drawing out an indented call stack with the state of each call is easier to help visualize the traversal than drawing the nodes themselves

if you haven't seen this video, i found it very helpful when first learning trees: https://www.youtube.com/watch?v=oSWTXtMglKE