Construct Binary Tree from Preorder and Postorder Traversal

Med

#0843Time: O(N^2), where N is the number of nodes. For each node, we might scan a significant portion of the `postorder` array and create new sub-arrays, both of which are O(N) operations. This leads to a quadratic time complexity.Space: O(N^2), where N is the number of nodes. The recursion depth can be O(N), and at each level, new arrays are created, leading to a quadratic space complexity in the worst case.

Algorithms

Divide and Conquer

Data structures

Array Hash Table Tree Binary Tree

Prompt

Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.

If there exist multiple answers, you can return any of them.

Example 1:

Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

Example 2:

Input: preorder = [1], postorder = [1]
Output: [1]

Constraints:

1 <= preorder.length <= 30
1 <= preorder[i] <= preorder.length
All the values of preorder are unique.
postorder.length == preorder.length
1 <= postorder[i] <= postorder.length
All the values of postorder are unique.
It is guaranteed that preorder and postorder are the preorder traversal and postorder traversal of the same binary tree.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly translates the properties of preorder and postorder traversals into a recursive algorithm. It identifies the root and then determines the bounds of the left and right subtrees by finding the left child's root in the postorder array. It then creates new sub-arrays for the left and right subtrees and calls itself recursively. While conceptually straightforward, this method is highly inefficient due to the overhead of creating array slices in each step.

Algorithm

Create a recursive function construct(pre, post).
Base Case: If the pre array is empty, return null.
Create a TreeNode for the root using pre[0].
If pre has only one element, return the root node as it's a leaf.
Identify the root of the left subtree, which is pre[1].
Linearly scan the post array to find the index of the left subtree's root. Let this be postIdx.
The number of nodes in the left subtree is leftSubtreeSize = postIdx + 1.
Create new arrays (slices) for the left and right subtrees from the pre and post arrays.
- Left subtree preorder: pre.slice(1, 1 + leftSubtreeSize)
- Left subtree postorder: post.slice(0, leftSubtreeSize)
- Right subtree preorder: pre.slice(1 + leftSubtreeSize, pre.length)
- Right subtree postorder: post.slice(leftSubtreeSize, post.length - 1)
Recursively call construct for the left and right subtrees and assign them to root.left and root.right.
Return the root.

Walkthrough

The fundamental idea relies on the traversal orders:

Preorder: Root -> Left -> Right
Postorder: Left -> Right -> Root

From this, we know that preorder[0] is the root of the current tree. If the tree is not just a single node, preorder[1] must be the root of the left subtree. We can then find this value (preorder[1]) in the postorder array. All elements in the postorder array up to and including this value belong to the left subtree. This allows us to determine the size of the left subtree.

Once we know the size of the left subtree, we can partition both the preorder and postorder arrays into three parts: the root, the left subtree's elements, and the right subtree's elements. We then make recursive calls on these smaller, newly created sub-arrays to build the left and right children of the root.

1import java.util.Arrays;2 3/**4 * Definition for a binary tree node.5 * public class TreeNode {6 *     int val;7 *     TreeNode left;8 *     TreeNode right;9 *     TreeNode() {}10 *     TreeNode(int val) { this.val = val; }11 *     TreeNode(int val, TreeNode left, TreeNode right) {12 *         this.val = val;13 *         this.left = left;14 *         this.right = right;15 *     }16 * }17 */18class Solution {19    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {20        if (preorder == null || preorder.length == 0) {21            return null;22        }23        TreeNode root = new TreeNode(preorder[0]);24        if (preorder.length == 1) {25            return root;26        }27 28        int leftRootVal = preorder[1];29        int leftSubtreeSize = 0;30        for (int i = 0; i < postorder.length; i++) {31            if (postorder[i] == leftRootVal) {32                leftSubtreeSize = i + 1;33                break;34            }35        }36 37        root.left = constructFromPrePost(38            Arrays.copyOfRange(preorder, 1, 1 + leftSubtreeSize),39            Arrays.copyOfRange(postorder, 0, leftSubtreeSize)40        );41 42        if (preorder.length > 1 + leftSubtreeSize) {43            root.right = constructFromPrePost(44                Arrays.copyOfRange(preorder, 1 + leftSubtreeSize, preorder.length),45                Arrays.copyOfRange(postorder, leftSubtreeSize, postorder.length - 1)46            );47        }48 49        return root;50    }51}

Complexity

Time

O(N^2), where N is the number of nodes. For each node, we might scan a significant portion of the `postorder` array and create new sub-arrays, both of which are O(N) operations. This leads to a quadratic time complexity.

Space

O(N^2), where N is the number of nodes. The recursion depth can be O(N), and at each level, new arrays are created, leading to a quadratic space complexity in the worst case.

Trade-offs

Pros

Easy to understand and implement.
Directly follows the definitions of the traversals.

Cons

Very inefficient in both time and space.
Creating new array slices in every recursive call leads to high memory usage and overhead.

This approach improves upon the previous one by eliminating the costly array slicing operations. Instead of creating new arrays for each recursive call, we pass indices that define the current working segments of the original preorder and postorder arrays. This significantly reduces memory usage and improves performance, but the time complexity remains quadratic because we still need to linearly scan the postorder array segment to find the boundary of the left subtree.

Algorithm

Create a helper recursive function build(preStart, preEnd, postStart, postEnd) that operates on indices of the original arrays.
Base Case: If preStart > preEnd, the current segment is empty, so return null.
Create a TreeNode for the root using preorder[preStart].
If preStart == preEnd, it's a leaf node, so return it.
Identify the left subtree's root value: leftRootVal = preorder[preStart + 1].
Linearly scan the postorder array from postStart to postEnd to find the index of leftRootVal. Let this be postIdx.
Calculate the number of nodes in the left subtree: leftSubtreeSize = postIdx - postStart + 1.
Make a recursive call to build the left subtree with updated indices: build(preStart + 1, preStart + leftSubtreeSize, postStart, postIdx).
Make a recursive call to build the right subtree with updated indices: build(preStart + leftSubtreeSize + 1, preEnd, postIdx + 1, postEnd - 1).
Return the root.

Walkthrough

To avoid the overhead of creating new arrays, we can define a recursive helper function that takes the start and end indices for the current subproblems in the preorder and postorder arrays. The logic for identifying the root, the left subtree's root, and the size of the subtrees remains identical to the first approach. The key difference is that instead of slicing, we calculate the new index boundaries for the recursive calls for the left and right children. This optimization improves space complexity from O(N^2) to O(N).

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {18        return build(preorder, 0, preorder.length - 1, postorder, 0, postorder.length - 1);19    }20 21    private TreeNode build(int[] pre, int preStart, int preEnd, int[] post, int postStart, int postEnd) {22        if (preStart > preEnd) {23            return null;24        }25 26        TreeNode root = new TreeNode(pre[preStart]);27        if (preStart == preEnd) {28            return root;29        }30 31        int leftRootVal = pre[preStart + 1];32        int postIdx = -1;33        for (int i = postStart; i <= postEnd; i++) {34            if (post[i] == leftRootVal) {35                postIdx = i;36                break;37            }38        }39 40        int leftSubtreeSize = postIdx - postStart + 1;41 42        root.left = build(pre, preStart + 1, preStart + leftSubtreeSize, post, postStart, postIdx);43        root.right = build(pre, preStart + leftSubtreeSize + 1, preEnd, post, postIdx + 1, postEnd - 1);44 45        return root;46    }47}

Complexity

Time

O(N^2). The linear scan to find the left subtree's root in the `postorder` array segment is performed for each of the N nodes, resulting in a quadratic time complexity.

Space

O(N) for the recursion stack. In the worst case of a skewed tree, the recursion depth can be N.

Trade-offs

Pros

More space-efficient than the array slicing method.
Avoids the overhead of object creation for new arrays.

Cons

The time complexity is still O(N^2) due to the linear scan in each recursive call.
Not efficient for large trees.

This is the most efficient approach. It optimizes the index-based recursive solution by eliminating the O(N) search in each step. By pre-processing the postorder array into a hash map, we can find the index of any element in O(1) time. This reduces the work done at each recursive step to constant time, leading to an overall linear time complexity for constructing the entire tree.

Algorithm

Before recursion, create a HashMap to store the mapping of each value in postorder to its index. This takes O(N) time.
Use the same recursive helper function build(preStart, preEnd, postStart, postEnd) as in the previous approach.
Base Case: If preStart > preEnd, return null.
Create a TreeNode for the root using preorder[preStart].
If preStart == preEnd, return the root.
Identify the left subtree's root value: leftRootVal = preorder[preStart + 1].
Instead of a linear scan, use the pre-computed HashMap to find the index of leftRootVal in postorder in O(1) time. Let this be postIdx.
Calculate the size of the left subtree: leftSubtreeSize = postIdx - postStart + 1.
Make recursive calls for the left and right subtrees with the calculated index boundaries, just like in the previous approach.
Return the root.

Walkthrough

The bottleneck in the previous approach was the repeated linear search to locate the root of the left subtree within the postorder array. We can eliminate this by pre-calculating the positions of all values. We first iterate through the postorder array and store each element's value and its index in a HashMap.

Now, inside our recursive function, when we need to find the index of the left subtree's root (preorder[preStart + 1]), we can simply look it up in our map. This is an O(1) operation. Since every other operation within a single recursive call is also O(1), and the function is called once for each node, the total time complexity becomes O(N).

1import java.util.HashMap;2import java.util.Map;3 4/**5 * Definition for a binary tree node.6 * public class TreeNode {7 *     int val;8 *     TreeNode left;9 *     TreeNode right;10 *     TreeNode() {}11 *     TreeNode(int val) { this.val = val; }12 *     TreeNode(int val, TreeNode left, TreeNode right) {13 *         this.val = val;14 *         this.left = left;15 *         this.right = right;16 *     }17 * }18 */19class Solution {20    private Map<Integer, Integer> postorderMap;21    private int[] preorder;22    private int[] postorder;23 24    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {25        this.preorder = preorder;26        this.postorder = postorder;27        this.postorderMap = new HashMap<>();28        for (int i = 0; i < postorder.length; i++) {29            postorderMap.put(postorder[i], i);30        }31        return build(0, preorder.length - 1, 0, postorder.length - 1);32    }33 34    private TreeNode build(int preStart, int preEnd, int postStart, int postEnd) {35        if (preStart > preEnd) {36            return null;37        }38 39        TreeNode root = new TreeNode(preorder[preStart]);40        if (preStart == preEnd) {41            return root;42        }43 44        int leftRootVal = preorder[preStart + 1];45        int postIdx = postorderMap.get(leftRootVal);46        47        int leftSubtreeSize = postIdx - postStart + 1;48 49        root.left = build(preStart + 1, preStart + leftSubtreeSize, postStart, postIdx);50        root.right = build(preStart + leftSubtreeSize + 1, preEnd, postIdx + 1, postEnd - 1);51 52        return root;53    }54}

Complexity

Time

O(N). Building the hash map takes O(N). The recursive function is called N times, with each call performing O(1) work (thanks to the map).

Space

O(N). We use O(N) space for the hash map and O(N) for the recursion stack in the worst case.

Trade-offs

Pros

Optimal time complexity of O(N).
It's a common and powerful pattern for solving tree construction problems from traversals.

Cons

Requires O(N) extra space for the hash map.

Solutions

Solution

1public class Construct_Binary_Tree_from_Preorder_and_Postorder_Traversal { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { /* preorder -> [1] [2,4,5] [3,6,7] postorder -> [4,5,2] [6,7,3] [root] */ public TreeNode constructFromPrePost ( int [] pre , int [] post ) { return helper ( pre , 0 , pre . length - 1 , post , 0 , post . length - 1 ); } // preL 和 preR 分别表示左子树区间的开头和结尾位置 // postL 和 postR 表示右子树区间的开头和结尾位置 TreeNode helper ( int [] pre , int preL , int preR , int [] post , int postL , int postR ) { if ( preL > preR || postL > postR ) { return null ; } // root node TreeNode node = new TreeNode ( pre [ preL ]); if ( preL == preR ) { // leaf node return node ; } // 找左子树的根结点(pre[preL + 1) 在 post[] 中的位置 // pre[preL + 1 here "+1" to skip above root node int idx = - 1 ; for ( idx = postL ; idx <= postR ; ++ idx ) { if ( pre [ preL + 1 ] == post [ idx ]) { break ; } } // left sub tree length: (idx - postL) // right sub tree length: node . left = helper ( pre , preL + 1 , preL + 1 + ( idx - postL ), post , postL , idx ); node . right = helper ( pre , preL + 1 + ( idx - postL ) + 1 , preR , post , idx + 1 , postR - 1 ); // postR - 1 to skip root return node ; } } } ////// class Solution { public TreeNode constructFromPrePost ( int [] pre , int [] post ) { int length = pre . length ; if ( length == 0 ) return null ; else if ( length == 1 ) return new TreeNode ( pre [ 0 ]); else { TreeNode root = new TreeNode ( pre [ 0 ]); int leftChild = pre [ 1 ]; int leftCount = 0 ; for ( int i = 0 ; i < length ; i ++) { if ( post [ i ] == leftChild ) { leftCount = i + 1 ; break ; } } root . left = constructFromPrePost ( Arrays . copyOfRange ( pre , 1 , 1 + leftCount ), Arrays . copyOfRange ( post , 0 , leftCount )); root . right = constructFromPrePost ( Arrays . copyOfRange ( pre , 1 + leftCount , length ), Arrays . copyOfRange ( post , leftCount , length - 1 )); return root ; } } }

1# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None ''' >>> a = [1,2,3,4,5] >>> a[0:2] [1, 2] so right index is exclusive ''' class Solution ( object ): def constructFromPrePost ( self , pre , post ): """ :type pre: List[int] :type post: List[int] :rtype: TreeNode """ if not pre or not post : return None root = TreeNode ( pre [ 0 ]) if len ( pre ) == 1 : return root idx = pre . index ( post [ - 2 ]) root . left = self . constructFromPrePost ( pre [ 1 : idx ], post [: idx - 1 ]) root . right = self . constructFromPrePost ( pre [ idx :], post [ idx - 1 : - 1 ]) return root ############ # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def constructFromPrePost ( self , preorder : List [ int ], postorder : List [ int ] ) -> TreeNode : n = len ( preorder ) if n == 0 : return None root = TreeNode ( preorder [ 0 ]) if n == 1 : return root for i in range ( n - 1 ): if postorder [ i ] == preorder [ 1 ]: root . left = self . constructFromPrePost ( preorder [ 1 : 1 + i + 1 ], postorder [: i + 1 ] ) root . right = self . constructFromPrePost ( preorder [ 1 + i + 1 :], postorder [ i + 1 : - 1 ] ) return root

1// OJ: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/ // Time: O(N^2) // Space: O(N) class Solution { private: TreeNode * construct ( vector < int > & pre , int preBegin , int preEnd , vector < int > & post , int postBegin , int postEnd ) { if ( preBegin >= preEnd ) return NULL ; auto node = new TreeNode ( pre [ preBegin ]); if ( preBegin + 1 < preEnd ) { int leftVal = pre [ preBegin + 1 ]; int postMid = find ( post . begin () + postBegin , post . begin () + postEnd - 1 , leftVal ) - post . begin (); int postLeftLength = postMid - postBegin + 1 ; node -> left = construct ( pre , preBegin + 1 , preBegin + 1 + postLeftLength , post , postBegin , postMid + 1 ); node -> right = construct ( pre , preBegin + 1 + postLeftLength , preEnd , post , postMid + 1 , postEnd - 1 ); } return node ; } public: TreeNode * constructFromPrePost ( vector < int >& pre , vector < int >& post ) { return construct ( pre , 0 , pre . size (), post , 0 , post . size ()); } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1public class Construct_Binary_Tree_from_Preorder_and_Postorder_Traversal { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { /* preorder -> [1] [2,4,5] [3,6,7] postorder -> [4,5,2] [6,7,3] [root] */ public TreeNode constructFromPrePost ( int [] pre , int [] post ) { return helper ( pre , 0 , pre . length - 1 , post , 0 , post . length - 1 ); } // preL 和 preR 分别表示左子树区间的开头和结尾位置 // postL 和 postR 表示右子树区间的开头和结尾位置 TreeNode helper ( int [] pre , int preL , int preR , int [] post , int postL , int postR ) { if ( preL > preR || postL > postR ) { return null ; } // root node TreeNode node = new TreeNode ( pre [ preL ]); if ( preL == preR ) { // leaf node return node ; } // 找左子树的根结点(pre[preL + 1) 在 post[] 中的位置 // pre[preL + 1 here "+1" to skip above root node int idx = - 1 ; for ( idx = postL ; idx <= postR ; ++ idx ) { if ( pre [ preL + 1 ] == post [ idx ]) { break ; } } // left sub tree length: (idx - postL) // right sub tree length: node . left = helper ( pre , preL + 1 , preL + 1 + ( idx - postL ), post , postL , idx ); node . right = helper ( pre , preL + 1 + ( idx - postL ) + 1 , preR , post , idx + 1 , postR - 1 ); // postR - 1 to skip root return node ; } } } ////// class Solution { public TreeNode constructFromPrePost ( int [] pre , int [] post ) { int length = pre . length ; if ( length == 0 ) return null ; else if ( length == 1 ) return new TreeNode ( pre [ 0 ]); else { TreeNode root = new TreeNode ( pre [ 0 ]); int leftChild = pre [ 1 ]; int leftCount = 0 ; for ( int i = 0 ; i < length ; i ++) { if ( post [ i ] == leftChild ) { leftCount = i + 1 ; break ; } } root . left = constructFromPrePost ( Arrays . copyOfRange ( pre , 1 , 1 + leftCount ), Arrays . copyOfRange ( post , 0 , leftCount )); root . right = constructFromPrePost ( Arrays . copyOfRange ( pre , 1 + leftCount , length ), Arrays . copyOfRange ( post , leftCount , length - 1 )); return root ; } } }

1# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None ''' >>> a = [1,2,3,4,5] >>> a[0:2] [1, 2] so right index is exclusive ''' class Solution ( object ): def constructFromPrePost ( self , pre , post ): """ :type pre: List[int] :type post: List[int] :rtype: TreeNode """ if not pre or not post : return None root = TreeNode ( pre [ 0 ]) if len ( pre ) == 1 : return root idx = pre . index ( post [ - 2 ]) root . left = self . constructFromPrePost ( pre [ 1 : idx ], post [: idx - 1 ]) root . right = self . constructFromPrePost ( pre [ idx :], post [ idx - 1 : - 1 ]) return root ############ # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def constructFromPrePost ( self , preorder : List [ int ], postorder : List [ int ] ) -> TreeNode : n = len ( preorder ) if n == 0 : return None root = TreeNode ( preorder [ 0 ]) if n == 1 : return root for i in range ( n - 1 ): if postorder [ i ] == preorder [ 1 ]: root . left = self . constructFromPrePost ( preorder [ 1 : 1 + i + 1 ], postorder [: i + 1 ] ) root . right = self . constructFromPrePost ( preorder [ 1 + i + 1 :], postorder [ i + 1 : - 1 ] ) return root

1// OJ: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/ // Time: O(N^2) // Space: O(N) class Solution { private: TreeNode * construct ( vector < int > & pre , int preBegin , int preEnd , vector < int > & post , int postBegin , int postEnd ) { if ( preBegin >= preEnd ) return NULL ; auto node = new TreeNode ( pre [ preBegin ]); if ( preBegin + 1 < preEnd ) { int leftVal = pre [ preBegin + 1 ]; int postMid = find ( post . begin () + postBegin , post . begin () + postEnd - 1 , leftVal ) - post . begin (); int postLeftLength = postMid - postBegin + 1 ; node -> left = construct ( pre , preBegin + 1 , preBegin + 1 + postLeftLength , post , postBegin , postMid + 1 ); node -> right = construct ( pre , preBegin + 1 + postLeftLength , preEnd , post , postMid + 1 , postEnd - 1 ); } return node ; } public: TreeNode * constructFromPrePost ( vector < int >& pre , vector < int >& post ) { return construct ( pre , 0 , pre . size (), post , 0 , post . size ()); } };

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.