algoadvance

You are given two integer arrays, preorder and postorder, where preorder is the preorder traversal of a binary tree, and postorder is the postorder traversal of the same tree. Construct and return the binary tree.

Example:

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

Constraints:

1. 1 <= preorder.length <= 30
2. preorder.length == postorder.length
3. preorder and postorder consist of distinct values between 1 and 1000.

Clarifying Questions

1. Are there any duplicate values in the arrays?
   • No, the values are distinct as per the constraint.
2. Can I assume the binary tree is a full binary tree?
   • No, we can’t assume the binary tree is full or complete.
3. Will the array always represent a valid preorder and postorder traversal of some binary tree?
   • Yes, it is guaranteed by the problem statement.

Strategy

1. Recursive Approach: The problem can be solved through a recursive approach by breaking down the problem based on the nature of preorder and postorder traversal.
2. Root Identification:
   • The first element in preorder is always the root of the tree.
   • The last element in postorder should also be the root and must be the same as the first element of preorder.
3. Subtree Construction:
   • In preorder, after the root, the next element is the left child node (for non-empty subtrees).
   • In postorder, the left and right children nodes are before the last root element.
4. Splitting the Tree:
   • We can use the position of the left child in the preorder list to find the boundary for left and right subtrees in the postorder list.

Code

# 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

def constructFromPrePost(preorder, postorder):
    if not preorder or not postorder:
        return None
    
    root_val = preorder[0]
    root = TreeNode(root_val)
    
    if len(preorder) == 1:
        return root
    
    # Find the left subtree root in preorder (second element)
    left_root_val = preorder[1]
    # Find the index of the left subtree root in postorder to split the tree
    left_root_index = postorder.index(left_root_val)
    
    # Left subtree in preorder is from 1 to left_root_index + 1 in preorder
    left_preorder = preorder[1:left_root_index + 2]
    # Right subtree in preorder is from left_root_index + 2 to end
    right_preorder = preorder[left_root_index + 2:]
    
    # Left subtree in postorder is from 0 to left_root_index
    left_postorder = postorder[:left_root_index + 1]
    # Right subtree in postorder is from left_root_index + 1 to end - 1 (minus the root)
    right_postorder = postorder[left_root_index + 1: -1]
    
    root.left = constructFromPrePost(left_preorder, left_postorder)
    root.right = constructFromPrePost(right_preorder, right_postorder)
    
    return root

Time Complexity

• The function makes a recursive call on each left and right subtree splitting the preorder and postorder arrays, and each splitting operation involves finding an index which is O(N) in the worst case.
• The overall time complexity can be considered as O(N^2) in the worst case due to the index search operation in each recursive step.

Make sure to test the function with different cases to ensure correctness.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?