Construct Binary Tree From Preorder And Postorder Traversal - Leetcode Solution

Problem Statement:

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

Note: You may assume that duplicates do not exist in the tree.

Example:

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]

Approach:

1. We know that in pre-order traversal, first node is always the root node, while in post-order traversal, the last node is the root node.

2. Therefore, we can use the pre-order traversal to find the root node, and then use post-order traversal to find the left and right subtrees.

3. Once we have the left and right subtrees, we can recursively build the tree.

Algorithm:

1. Create a function called buildTree where we will pass the two arrays preorder and postorder.

2. The first element in the preorder array will be the root of the tree. Create a new node for the root and assign it to the variable root.

3. We will create an index variable i and initialize it with 0.

4. The next step is to find the index of root in the postorder array.

   For that, we will loop through the postorder array starting from the end, until we find the index of the root element. When we find the index of the root element, we break the loop.

   We also increment the value of i. The value of i will be used to divide the preorder array into left and right subtrees.

   The formula to calculate the index of root in the postorder array is: indexOfRoot = length of the postorder array - i - 1.

5. Divide the preorder array into left and right subtrees.

   The left sub-tree will start from the index 1, and end at index i. The right sub-tree will start from the index i+1, and end at the last index of preorder array.

   Create two new arrays for left and right subtrees.

   leftPreorder = preorder[1:i+1] rightPreorder = preorder[i+1:end]

6. Divide the postorder array into left and right subtrees.

   The left sub-tree will start from the index 0, and end at the index indexOfRoot-1. The right sub-tree will start from the index indexOfRoot, and end at the index length of postorder array -1.

   Create two new arrays for left and right subtrees.

   leftPostorder = postorder[0:indexOfRoot] rightPostorder = postorder[indexOfRoot:end-1]

7. Repeat steps 2 to 6 recursively for the left and right subtree.

8. Return the root of the tree.

Pseudocode:

function buildTree(preorder, postorder):

root = new TreeNode(preorder[0])

i = 0 while i < len(postorder): if postorder[i] == root.val: break i += 1

indexOfRoot = len(postorder) - i - 1

leftPreorder = preorder[1:i+1] rightPreorder = preorder[i+1:]

leftPostorder = postorder[0:indexOfRoot] rightPostorder = postorder[indexOfRoot:len(postorder)-1]

root.left = buildTree(leftPreorder, leftPostorder) root.right = buildTree(rightPreorder, rightPostorder)

return root

Time Complexity: O(N^2), where N is the number of nodes in the tree. In the worst case, if all the nodes have only left or right child, then the recursive function will be called N times for each node.

Space Complexity: O(N), where N is the number of nodes in the tree. The space required by the call stack will be proportional to the height of the tree, which in the worst case will be N for a skewed tree.

Solution in Python:

class TreeNode: def init(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right

class Solution: def buildTree(self, preorder: List[int], postorder: List[int]) -> TreeNode: if not preorder: return None

    root = TreeNode(preorder[0])
    
    i = 0
    while i < len(postorder):
        if postorder[i] == root.val:
            break
        i += 1
    
    indexOfRoot = len(postorder) - i - 1
    
    leftPreorder = preorder[1:i+1]
    rightPreorder = preorder[i+1:]
    
    leftPostorder = postorder[0:indexOfRoot]
    rightPostorder = postorder[indexOfRoot:len(postorder)-1]
    
    root.left = self.buildTree(leftPreorder, leftPostorder)
    root.right = self.buildTree(rightPreorder, rightPostorder)
    
    return root

Conclusion:

In this problem, we have learned how to construct a binary tree from the given pre-order and post-order traversal arrays. The key idea is to use the pre-order traversal to find the root of the tree and the post-order traversal to find the left and right subtrees. We have also provided the detailed algorithm, pseudocode, time complexity, and space complexity of the solution.

1