## Binary Trees Traversal Recursive vs. Iterative Photo reference: https://computersciencewiki.org/index.php/Binary_tree

This neat little trick above saved me a lot of pain and is much quicker to get the traversals. Just think preorder = left, inorder = center, postorder = right. Then weave the string from the top left, to the bottom, to the center, and around until you get to the top right. Wherever the string would 'hook' into a line, write down that number as the next one in that type of traversal.

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

Every recursive problem can be done iteratively using a stack. Recursive calls are simply utilizing the call stack that is an inherent part of the programming language. Don't forget to take into account the space the stack/recursive calls take up when doing the O notation for space!

Recursive solution:
```public IList InorderTraversal(TreeNode root)
{
List result = new List();

Helper(root, result);

return result;
}

public void Helper(TreeNode root, List result)
{
if (root == null) return;

Helper(root.left, result);
Helper(root.right, result);
}
```
Time: O(n)
Space: O(log n) on average. O(n) worst case if tree is one giant linked list going in one direction.

Iterative solution using a stack:
```public IList InorderTraversal(TreeNode root)
{
List result = new List();
Stack stack = new Stack();

TreeNode curr = root;

while(curr != null || stack.Count != 0)
{
while(curr != null)
{
stack.Push(curr);
curr = curr.left;
}

curr = stack.Pop();