# Stacks or Recursion

Optional Node

While certain coding problems can be solved most effectively with recursion, you can also learn how to do them without it.

### Trees, Recursion & Stacks

Trees are recursive structures, so most tree algorithms use recursion to 'branch out' through the tree.

Q: How does the compiler keep track of all these recursive calls?
A: Each function call is placed on a Stack, and is popped off the stack as the results are returned.
Q: Could I use my own Stack to track results instead of using recursion?
A: Yes, you can always replace recursion with a Loop and a Stack. It will usually make your code much messier, but there are rare occasions when you'll want to do it.

### Challenge

In How Tall is the Tree?, you could find the height of the tree using recursion. Can you solve the same problem by using a Stack and Loop instead?

Details

The height of a Tree is the number of Nodes from the Root to the lowest Leaf. The Tree does not need to be balanced.

For example, in the tree below, the height is 4:

As discussed in trees, You will given a Tree stored in a list. Find and print the height of the Tree.

### More Challenges

See if you can solve other recursion challenges with a Stack and Loop instead of recursion:

### Challenge

Us a Stack and Loop to go through a tree and find its height. Print each tree's height on a newline.

Alternatively, you can try out Learneroo before signing up.

• #### Panashe Fundira

Does this really require a stack? If you make the observation that each level in the level order representation has 2n - 1 nodes (including zeros), where `n` is the number of the tree

• #### Panashe Fundira

2n - 1 in my previous comment. Tried to use superscript in markdown, didn't work

• #### Learneroo

@Panashe, that's true with the current input format, but for the full challenge you should assume you're just given the tree nodes without an array.