Given the root of a binary tree, return the inorder traversal of its nodes’ values.

🪞 Reflections

I don’t remember what inorder traversal means (or preorder or postorder).

I can’t infer what it means based on the examples in this problem.

The name doesn’t seem to imply the meaning.

So I’m not going to try this problem yet. Instead, I’ll do some research and brush up on these terms.

🔍 Research

🌲 Tree Traversal
➡️ Got it. In-order visits the parent in-between the children. Thankfully, an in-order traversal returns nodes in-order for a binary search tree.

In-order traversal

flowchart
2 --> 1
2 --> 3

📚 A stack (explicitly or implicitly via the call-stack) will be useful during implementation.

Back to our problem

It still took a bit of planning to settle on an implementation.
Initially, I was thinking about how to use a stack for an iterative solution.
I was not at all certain about this algorithm, so I pivoted to a recursive plan.
I was confident in the recursive plan, which yielded a very concise implementation.
I found 1 bug during my 4th test case, which included a sub-tree to traverse.

After finishing my timed trial, I did various (untimed) refactorings, including refactoring to use an iterative algorithm with an explicit stack.
Refactored solutions are below the first.

🪞 Reflections

It’s good to brush up on tree traversals

When a recursive implementation is natural, use it

If we must define an iterative version…

define the recursive version first

identify the variables we’ll need in our stack frames

figure out how to explicitly discriminate between the base case and recursive calls

convert function arguments to an appropriate stack frame and push it onto a stack

while the stack is not empty, process the next frame (which may involve pushing more frames on the stack)

30 minutes is not too bad for my first time implementing this in a long time

Studying to familiarize myself with the concepts before attempting the problem worked well

Practicing common algorithms like this is probably a good idea to speed things up