We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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.
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).
Tree: Postorder Traversal
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).
Iterative Way Tutorial Link : Binary tree postOrder