# My non-recursive solution, use a stack instead of resursion

• My idea is simple. For each node, I build it's left child first.Then build it's left child's left child....Build a stack to store the node I have built. When the iteration reached left corner of the tree, trace back the stack and build right child for each node.
How do we find the left corner ? The first element of inorder-traverse-array is the left corner of the tree.
Here is my solution.

``````class Solution {
public:
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
if (preorder.empty())
return NULL;
TreeNode* now = new TreeNode(preorder.front());
preorder.erase(preorder.begin());
stack<TreeNode*> s;
s.push(now);
while (true){
if (s.top()->val == inorder.front()){
//build right child and store
//the first element of the inorder-array is left corner
TreeNode* store = NULL;
while (!s.empty() && s.top()->val == inorder.front()){
store = s.top();
s.pop();
inorder.erase(inorder.begin());
}
if (inorder.empty())
break;
TreeNode *temp = new TreeNode(preorder.front());
preorder.erase(preorder.begin());
store->right = temp;
s.push(temp);
}
else{
//build left child and store
TreeNode *temp = new TreeNode(preorder.front());
preorder.erase(preorder.begin());
s.top()->left = temp;
s.push(temp);
}
}
return now;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.