You are viewing a single comment's thread. Return to all comments →
How would you solve this without using recursion?
Create a list or an array to store traversal ie as you go left, until you encounter any leaf, then move back up and store those values. When you encounter a previous node with a right subtree, repeat the steps.
Why would you want to?
To avoid stack overflow if the tree is very high.
You are more than likely to run out of memory trying to maintain the data structure than the recursive calls. If you use an assumption that a 64 bit machine uses a 64 bit pointer for the function address then you are pushing 16 bytes per call (8 bytes for the function address and 8 bytes for the heap address of the data object). When you use the stack object to store the data object you have the overhead of the stack object and if that stack object is not implemented correctly the possibility of the data object being passed by value and not by refernce. In this case that could be anywhere from 18 to 24 bytes per object (depending on the size of the int for the data).
Tutorial Link : Binary tree postOrder