 Below is our original solution, which uses a recursive function `height`. Try converting this code to iterative code, so that the function doesn't call itself. ``` def height(node): if node is None: return 0 return 1 + max( height(node.left), height(node.right) ) ``` The trick is to put the node in the stack, and along with it, keep a label whether or not we're calling it for the first time. If this is the first time we're calling it, we should compute height on the left node first and then com

Iterative Tree Height

-----problem-----

 Below is our original solution, which uses a recursive function `height`. Try converting this code to iterative code, so that the function doesn't call itself.

```

def height(node):
    if node is None:
        return 0
        
    return 1 + max(
        height(node.left), 
        height(node.right)
    )
```



-----solution-----

The trick is to put the node in the stack, and along with it, keep a label whether or not we're calling it for the first time. If this is the first time we're calling it, we should compute height on the left node first and then come back. Then when we come back for the second time, we're ready to compute the height.


Notice that we add elements to the stack in reverse order because stacks are last-in-first-out.

We also store all the heights we've computed in some data structure so we can access them wherever we need them. (You can make this more general/readable, but since we're just implementing a less convenient and less general version of Python's Call Stack, it's not really worth the thought).

\answer



\tc $O(n)$

\sc $O(n)$. The stack grows in the same exact way as the recursive solution, so it has the same space complexity.





Iteration

Iterative Tree Height