Stacks or RecursionOptional 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.
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?
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.
See if you can solve other recursion challenges with a Stack and Loop instead of recursion: