# Binary Tree In-Order Traversal

The prompt may be found on leetcode.

- Iterate over the current nodes left subtree,
- Iterate the node itself,
- Iterate the nodes right subtree.

## Analysis

The recursive solution is trivial, what is more tricky is the iterative solution, which would likely involve a queue or a stack. The solution with the stack is somewhat tricky to implement, but a drawing can help:

```
Iteration 1:
Left until no further left to go.
Stack all nodes traversed going left.
stack = [A, B]
A
/^\
B 0 C
^ / \
1 D E
/ \
F G
Unstack and yield B, and choose its right node as the current node.
Iteration 2:
There is no current node, and therefore nothing to add to the stack.
stack = []
So take ``A`` from the stack instead since the current node is none.
Yield A, and choose its right node as the current node.
Iteration 3:
The current node is C. Go left and C, D, and F to the stack.
stack = [C, D]
A
/ \
B C
/^\
D 0 E
/^\
F 1 G
^
2
Take F off of the stack, and yield it.
Now there is no current node.
Iteration 4:
The current node does not exist, so we take D from the top of the stack.
Now G is the current node.
stack = [C]
Iteration 4.
The current node G is added to the stack, then removed and yielded since
there is nothing to the left of it.
There is nothing right of G, so the current node is none.
stack = [C]
Iteration 5:
There is no current node so C is take from the top of the stack.
C is yielded and the current node is E.
stack = []
Iteration 6:
There is nothing left of E so nothing is added to the stack and E is yielded.
There is nothing right of E either, so the recursion should stop.
```

## Solutions

### The Trivial Solution

I did two variations of the trivial solution. One using an iterator and another using a list to append to. I did this mostly to gain insights into performance.

The iterator solution placed an an acceptable \(80\%\) in runtime and \(68\%\) in memory usage.

```
class SolutionTrivial:
def _inorderTraversal(self, root: TreeNode) -> Iterator[int]:
if root.left is not None:
yield from self._inorderTraversal(root.left)
yield root.val
if root.right is not None:
yield from self._inorderTraversal(root.right)
def inorderTraversal(self, root: TreeNode | None) -> list[int]:
if root is None:
return list()
return list(self._inorderTraversal(root))
```

The appending solution placed at an yucky \(42\%\) in runtime and an abominable \(18\%\) in memory usage.

### The Nontrivial Solution

The nontrivial solution was not nearly as performant as the trivial solution, with \(64\%\) quantile in runtime and \(18\%\) quantile in memory. However it is a good exercise in using stacks.

```
class Solution:
def _inorderTraversal(self, root: TreeNode):
list[TreeNode] = []
stack: | None = root
node: TreeNode while stack or node is not None:
# If left is found, keep going left
while node is not None:
stack.append(node)= node.left
node
# When no left is found, yield value. Node is ``None`` so use the
# top of the stack.
= stack.pop()
node yield node.val
# Now that the top of the stack has been used, this will be added
# to the stack in the nested ``while`` loop.
= node.right
node
def inorderTraversal(self, root: TreeNode | None):
if root is None:
return list()
return list(self._inorderTraversal(root))
```