I recently had an assignment for an advanced coding class where I was to create a Binary tree from inorder and preorder traversals. I first started out by creating my ADT for binary trees and working with that to create a new tree. The way I worked it was that I started by storing inorder traversal in an array and preorder in a queue and then I went through dividing the array into smaller arrays and passing it to the function again, recursively. The base case was when there was only one element in the array, i.e. a leaf. and this was returned by the function.
The problem I encountered was that my tree had a destructor and was being destroyed before the function could send it back since it was declared as a local variable for the setupFunction. I tried everything from pointers to references but everytime the subtree was corrupted.
I did end up converting the recursion into a while loop. But my question is, if you are trying the return a custom ADT from a recursive call, how should you do it?