Stacks or Recursion
Optional NodeWhile 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
nis 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 PM2n - 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.