given two arrays representing preorder and postorder traversal of a full binary tree construct the binary tree and print the inorder traversal of the tree a full binary tree has either 0 or 2 children algorithm 1 assign the first element of preorder array as root of the tree 2 find the same element in the postorder array and divide the postorder array into left and right subtree 3 repeat the above steps for all the elements and construct the tree eg pre 1 2 4 8 9 5 3 6 7 post 8 9 4 5 2 6 7 3 1 tree 1 2 3 4 5 6 7 8 9 output 8 4 9 2 5 1 6 3 7 recursive function that constructs tree from preorder and postorder array preindex is a global variable that keeps track of the index in preorder array preorder and postorder array are represented are pre and post respectively low and high are the indices for the postorder array base case if only one element in the subarray return root find the next element of pre in post use index of element present in postorder to divide postorder array to two parts left subtree and right subtree main function that will construct the full binary tree from given preorder and postorder array prints the tree constructed in inorder format recursive function that constructs tree from preorder and postorder array preindex is a global variable that keeps track of the index in preorder array preorder and postorder array are represented are pre and post respectively low and high are the indices for the postorder array base case if only one element in the subarray return root find the next element of pre in post use index of element present in postorder to divide postorder array to two parts left subtree and right subtree main function that will construct the full binary tree from given preorder and postorder array prints the tree constructed in inorder format
class TreeNode:

    def __init__(self, val, left = None, right = None):
        self.val = val
        self.left = left
        self.right = right

pre_index = 0
        
def construct_tree_util(pre: list, post: list, low: int, high: int, size: int):
    

    global pre_index

    if pre_index == -1:
        pre_index = 0
  
    
    
    if(pre_index >= size or low > high):
        return None

    root = TreeNode(pre[pre_index])
    pre_index += 1

    
    if(low == high or pre_index >= size):
        return root

    
    i = low
    while i <= high:
        if(pre[pre_index] == post[i]):
            break

        i += 1

    
    
    if(i <= high):
        root.left = construct_tree_util(pre, post, low, i, size)
        root.right = construct_tree_util(pre, post, i+1, high, size)

    return root


def construct_tree(pre: list, post: list, size: int):
    

    global pre_index
    root = construct_tree_util(pre, post, 0, size-1, size)

    return print_inorder(root)



def print_inorder(root: TreeNode, result = None):
    
    if root is None:
        return []
    if result is None: 
        result = []
        
    print_inorder(root.left, result)
    result.append(root.val)
    print_inorder(root.right, result)
    return result

if __name__ == '__main__':
    pre = [1, 2, 4, 5, 3, 6, 7]
    post = [4, 5, 2, 6, 7, 3, 1]
    size = len(pre)

    result = construct_tree(pre, post, size)

    print(result)