Python implementation: def postorder(preorder, inorder): if len(preorder) <= 1: return preorder v = preorder[0] preorder = preorder[1:] pivot = inorder.find(v) left = inorder[0:pivot] right = inorder[pivot+1:] return postorder(preorder[:len(left)], left) + postorder(preorder[len(left):], right) + v print postorder('421356', '123456')

Here is the code for the answer explained above (the use of std::vector is inefficient): std::vector postorder(std::vector& preorder, std::vector& inorder, int min_pos, /* Position of min value of subtree in inorder representation */ int max_pos, /* Position of max value of subtree in inorder representation */ int& next_root_pos /* Index in preorder representation for finding next root node */ ) { std::vector res; // Value of the root for the current tree int root = preorder[next_root_pos]; // Find the position of this value in the preorder traversal int root_in_inorder_index = 0; while (inorder[root_in_inorder_index] != root) root_in_inorder_index++; // Left subtree if (min_pos != root_in_inorder_index) { next_root_pos++; std::vector left = postorder(preorder, inorder, min_pos, root_in_inorder_index - 1, next_root_pos); res.insert(res.end(), left.begin(), left.end()); } if (max_pos != root_in_inorder_index) { // Right subtree next_root_pos++; std::vector right = postorder(preorder, inorder, root_in_inorder_index + 1, max_pos, next_root_pos); res.insert(res.end(), right.begin(), right.end()); } // Current element res.push_back(root); return res; }

You can rebuild the tree by recursively dividing the inorder string representation into to parts: the left sub-tree and the right sub-tree. But in order to do that, you need to find the pivot that would be the root node. You know that this pivot is the first element in the preorder representation. When you go through the tree recursively, go on the left sub-tree first. The next pivot (the root of the left subtree), is always the next value in the preorder representation. That is why you need to keep a reference to the next root to be considered, a pointer to a position in the preorder string, that would be incremented. Keep track of the min and max position of the subtree you are considering. If min == max, you are on a leaf node, just return it. Otherwise, the postorder string reprensation is the concatenation of postorder(left sub tree) + root + postorder(right sub tree).