Stacks or Recursion

Optional Node
Collapse Content

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:

binary tree

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

  • 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

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

  • @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.

Contact Us