# Solving Leetcode Interviews in Seconds with AI: Construct Binary Tree from Preorder and Postorder Traversal


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "889" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> 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.  

	# Explanation
	Here's the breakdown of the solution:

*   **Root Identification:** The first element of the `preorder` array is always the root of the (sub)tree. The last element of the `postorder` array is also the root of the (sub)tree.
*   **Left Subtree Boundary:** Find the index of the left child (the second element in `preorder`) in `postorder`. Everything to the left of this index forms the left subtree in `postorder`. The size of the left subtree can be inferred.
*   **Recursive Construction:** Recursively construct the left and right subtrees using the identified boundaries in both `preorder` and `postorder` arrays.

*   **Time & Space Complexity:** O(N), where N is the number of nodes in the tree. Space complexity is O(N) due to the recursion stack.

	
	# Code
	```python
	class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def constructFromPrePost(preorder, postorder):
    """
    Reconstructs a binary tree from its preorder and postorder traversals.

    Args:
        preorder: A list of integers representing the preorder traversal.
        postorder: A list of integers representing the postorder traversal.

    Returns:
        The root of the reconstructed binary tree.
    """

    def buildTree(pre_start, pre_end, post_start, post_end):
        if pre_start > pre_end:
            return None

        root_val = preorder[pre_start]
        root = TreeNode(root_val)

        if pre_start == pre_end:
            return root

        left_child_val = preorder[pre_start + 1]
        left_child_index_in_post = postorder.index(left_child_val)

        left_subtree_size = left_child_index_in_post - post_start + 1

        root.left = buildTree(
            pre_start + 1, pre_start + left_subtree_size,
            post_start, left_child_index_in_post
        )

        root.right = buildTree(
            pre_start + left_subtree_size + 1, pre_end,
            left_child_index_in_post + 1, post_end - 1
        )

        return root

    return buildTree(0, len(preorder) - 1, 0, len(postorder) - 1)
	```