Courtesy of the post by lizhuogo. Details see
I thought his explanation is still a bit difficult to understand so I try to give a high-level understanding of this approach and the fundamental reason why it works as intended.
The key here is knowing the patterns of serialized list of inorder and postorder
If we traverse from root to the left child and back up, both inorder
and postorder traversals give us the same sequence, i.e. they are in
the same direction.
1 / 2 inorder: [1, 2] postorder: [1, 2]
whereas if we traverse from root to right child and back up, inorder and postorder
gives us sequences that are reverse of each other.
1 \ 2 inorder: [1, 2] postorder: [2, 1]
Using this observation, and the fact that the last member in postorder array is
the root of current subtree, we can traverse from right to left of the serialized
lists and build left and right child accordingly.
If we see postorder and inorder are of same value, we build the left child, else
we build the right child. After each operation, we store the newly created node
on stack to be the new root of the current subtree of size 1 and later traverse back
A stack is helpful for storing them because each pop let us go back up a level to
the parent of our current root.
Code in Python below with comments:
def buildTree(self, inorder, postorder): if len(inorder) == 0: return None root = TreeNode(postorder[-1]) stack = [root] # array indexes, i for inorder array, p for postorder array i = len(inorder) - 1 p = len(postorder) - 2 # initially root already 'popped' off postorder and stored in stack # we store values off postorder array and compare top of stack with # right most member of inorder array (indexed by i) while True: # top of stack is same as right most entry of inorder. The first time it # happens means we reached root of current tree. Then we keep removing them # since we already built right child nodes with them and they are on stack just so we # can traverse back up. See the else branch for the actual creation of right child. if stack[-1].val == inorder[i]: n = stack.pop() i -= 1 if i==-1: break if stack and inorder[i] == stack[-1].val: # keep removing these values, that is, traverse back up continue # finished all the right branch and root itself, now we build left child # 'n' here was popped from stack which gave us the current root. n.left = TreeNode(postorder[p]) p -= 1 stack.append(n.left) else: # mismatch values means we should build right child for current root n = TreeNode(postorder[p]) p-=1 stack[-1].right = n stack.append(n) return root