# Construct Binary Tree from Preorder and Postorder Traversal

• Given inorder and postorder traversal of a binary tree, construct the binary tree.

Note:

• You may assume that duplicates do NOT exist in the tree.
• Unlike constructing binary trees from in-order and pre/post-order sequences, pre-order and post-order sequences do not uniquely identify one binary tree. However, you just need to construct any one of the possible trees so long as its traversals sequence matches given sequences.

• @lucascho Could yo provide company's tag and some example if it ispossible? Thank you

• Sure. Some examples below:

``````1.
"""
_1_
"""
pre = [1]
post = [1]

2.
"""
_____1
/
2
"""
pre = [1, 2]
post = [2, 1]

3.
"""
1_____
\
2
"""
pre = [1, 2]
post = [2, 1]

4.
"""
_____2_____
/           \
3             4
"""
pre = [2, 3, 4]
post = [3, 4, 2]

5.
"""
_____7_____
/           \
__10__         __2_
/      \       /    \
4        3     _8    20
\   /
1  11
"""
pre = [7, 10, 4, 3, 1, 2, 8, 11, 20]
post = [4, 1, 3, 10, 11, 8, 20, 2, 7]

6.
"""
___7___
/        \
__6          8__
/                \
_5_                 9_
/                      \
_4_                      _10_
/   \                    /    \
_2    3                   11    12_
/                                   \
1                                     15
"""
pre = [7, 6, 5, 4, 2, 1, 3, 8, 9, 10, 11, 12, 15]
post = [1, 2, 3, 4, 5, 6, 11, 15, 12, 10, 9, 8, 7]
``````

Note that for example 2 and 3, the two sequences are the same but can give different binary trees due to ambiguity of left or right child during construction.

If needed, I can provide more test cases and solutions I wrote for this problem.

This question did not come from actual company interviews but rather a derived problem from LeetCode problems 'construct binary tree from inorder and preorder' and 'construct_binary tree from inorder and postorder'. IMHO, this problem goes one step further to test the understanding of binary tree traversals thus I posted it here for reference.

• @lucascho How about this question? It is probably a different question, since it is a generic n-ary tree, but also revolve around constructing tree from preorder and postorder traversal.

• @1337c0d3r Thanks for the link.

Indeed that problem is similar and more generic in the sense that more children are allowed. The big difference is in the format of how the data input. In the generic case, iterators are provided as well as an isLeaf() function to help guiding traversal. While this one and other LeetCode problems use serialized lists, which would impact implementation of the algorithm.

Interesting. Thanks.

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