Some people introduce tree traversals using a Stack, but that view is completely useless - recursion is the key here.

To solve this problem, we want to write a function that visits every node in the tree. We'll call the function visitAll.

1. Recursion

To visit all the nodes in the tree, you need to do something on the current node, and also on all the left and right children. There are a few ways to write a recursion that does this.

Here's one way we can write the recursion:

Here's another:

And another:

These 3 recursions each have their own name. More on this later.

2. Base case

All 3 recursions will keep calling themselves on lower and lower nodes in the tree. Eventually, a null node will be reached, in which case the recursion will break. This means we need a base case for null nodes. It's pretty obvious that visiting all the nodes in a null tree is the same as doing nothing, so here's the base case for all 3 recursions:

3. Code

We can code each of these up by combining the recursion and base case.

Here's the code for the first recursion:

This code is called a preorder traversal, because for any node in the tree, do_something will get called on the current node before (or "pre") any of the children. Here's a visual of this:

Here's the code for the second recursion:

This code is called an inorder traversal, because for any node in the tree, do_something will get called "in order". It first gets called on all the left children, and then on the current node, and then on all the right children. Here's a visual of this:

Here's the code for the third recursion:

This code is called a postorder traversal, because for any node in the tree, do_something will get called on the current node after (or "post") all the children. Here's a visual of this:

All 3 of these traversals are called DFS or "depth-first-search". This is because recursion always repeats the same process over and over, like "go left" or "go right", before doing anything else. This means recursions always step deeper into the tree, and are "depth-first". Literally every recursion is a DFS.

Time Complexity The amount of time depends on what you fill in for do_something, but if you do somthing simple like printing out the value, this is $O(n)$, since you're visiting all $n$ nodes in the tree.

Space Complexity Every recursion needs space for its Call Stack. Assuming do_something doesn't store anything, the Call Stack causes the space complexity to be $O(n)$ for trees in general and $O(\log n)$ for balanced trees.