Preorder tree traversal recursion?

Question

I know the recursive implementation for a preorder tree traversal, but I’m not sure how it works. Like when it goes through the very first branch until it gets to the last left leaf, I understand how it works up to that. But I don’t understand how it goes back up to a node that has a right subtree.

Say the root has 2 children and those children each have 2 children. The base case would be when the node passed in is null , beginning with the root. It would first print the root, then call the function on the root’s left node, print that node, and then print the left node of that node. Then, The leftmost node will check its left and right which are both null. But how does the function go back up the subtree to process the right node of the first left child?

Answer 1

Recursion does that for you. The call stack remembers every nested function call, and when a function returns you automatically go back up one step.

Here's a preorder tree map function:

void preorder_map(treenode t, function f) {
t.value = f(t.value);

if(t.leaf) return;

preorder_map(t.left, f);
preorder_map(t.right, f);
}

Once the first recursive call to preorder_map finishes, we do the second one.

It's not much different, than, say

burger make_cheeseburger() {
buns b;

add_meat(b);
add_cheese(b);
return b;
}

We know that `add_meat` must finish some time, yes? And after that, `add_cheese` runs.

It's the same with `preorder_map`. We know that `preorder_map(t.left, f);` terminates eventually, and after that we process the right subtree.

Here's how I think about recursion: You pretend like the function you are writing is already implemented correctly, so the recursive call will always do the correct thing. Then you just have to write some glue code to make it work.

Answer 2

https://code.sololearn.com/WgmyYnvs256O/?ref=app
https://code.sololearn.com/Ww7I0BEwHf33/?ref=app