Tail Recursion & Iterative way to traversal a binary tree (inorder)

First of all, introduce the recursive way to do in-order traversal of a binary tree, which is trivial XD. 

The following function is to flatten a binary tree into an array that is traversed in-order.

def inorder(root):
    if root == None:
       return []
    else:
       lt = inorder(root.left) 
       rt = inorder(root.right)
       return lt + [root.val] + rt

This is the standard way to do traversal on a binary tree, the same technique could be used to do pre-/post-traversal as well. However, what could we do if recursion is not allowed? Now let's introduce one phenomenon called 'Tail Recursion'

Here is a good resource to learn more about tail recursion

Tail Recursion means that in the end of a recursion function, it jumps back to its start with arguments reduced/shrinks.

Example that is NOT a Tail Recursion:

def factorial(n):
   if n == 1:
      return 1
   else:
      return n*factorial(n-1)

Even though that the recursion happens at the end of the function, it is not PURELY the recursion itself, so it is NOT Tail Recursion.

This definition is not tail-recursive since the recursive call to factorial is not the last thing in the function (its result has to be multiplied by n)

Example that is a Tail Recursion:

def factorial(n, accumulator):
   if n == 1:
       return accumulator
   else:
       return factorial(n-1, n * accumulator) 

This is definitely a Tail Recursion, since the last thing in the function is nothing but goes back to the function itself. Tail Recursion could be easily converted to a 'while' loop.

def factorial(n, accumulator):
    c = n
    while c != 1:
       accumulator *= c
    return accumulator

very intuitive, or?

The reason why sometimes iteration is better than recursion is because:

Recursive procedures call themselves to work towards a solution to a problem. In simple implementations this balloons the stack as the nesting gets deeper and deeper, reaches the solution, then returns through all of the stack frames. This waste is a common complaint about recursive programming in general.

Let's look back at recursion of inorder traversal:to be continued