# 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.

Please sign in or sign up to submit answers.

Alternatively, you can try out Learneroo before signing up.

## Comments

## Panashe Fundira

Jun 17, 7:32 PMDoes 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 treelevel, then you just have to find the lowest level that has a non-zero by iterating from the back-end of the array.

## Panashe Fundira

Jun 17, 7:33 PM2

^{n - 1}in my previous comment. Tried to use superscript in markdown, didn't work## Learneroo

Jun 18, 8:29 PM@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.