Understand Construct Binary Tree from Preorder and Postorder Traversal Problem

Problem Name: Construct Binary Tree from Preorder and Postorder Traversal

Problem Description:

Construct Binary Tree from Preorder and Postorder Traversal

Problem Statement

You are given two arrays representing the preorder and postorder traversals of a binary tree with unique values. Your task is to reconstruct the binary tree from these traversals and return its root.

Preorder Traversal: Visit the root first, then the left subtree, and finally the right subtree.
Postorder Traversal: Visit the left subtree first, then the right subtree, and finally the root.

If multiple valid trees exist, you can return any one of them.

Task

Implement a function that reconstructs the binary tree given:

preorder: an array of integers representing the preorder traversal.
postorder: an array of integers representing the postorder traversal.

Test Cases

Test Case 1

Input:

  "preorder": [1, 2, 4, 5, 3, 6, 7],
  "postorder": [4, 5, 2, 6, 7, 3, 1]

binary tree Output:

[1,2,3,4,5,6,7]

Test Case 2

Input:

  "preorder": [10, 20, 40, 50, 30, 60],
  "postorder": [40, 50, 20, 60, 30, 10]

binary tree OUTPUT:

[10,20,30,40,50,60]

Constraints

The number of nodes is between 1 and 30.
All values in preorder are unique.
postorder is a permutation of preorder and represents the postorder traversal of the same tree.

Approach

Identify the Root:
- The first element in preorder is the root of the tree.
- The last element in postorder is also the root.
Divide and Conquer:
- Use the next element in preorder (after the root) to determine the boundary of the left subtree in postorder.
- Recursively construct the left subtree using the corresponding segments from both arrays.
- Similarly, construct the right subtree with the remaining segments.
Construct the Tree:
- Combine the results from the recursive calls to form the entire binary tree.
- Return the root of the constructed tree.

Category:
Leetcode Problem of the Day

Programming Language:
Java

Reference Link:

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/description/

Online IDE

Scroll down for output

Java

Output:

Loading component...

Tracking code (View only. In case you want to track the code, click this button):

Main Function:

Main Function is not defined.

Helper Function:

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]

public static TreeNode constructFromPrePost(int[] pre, int[] post) {

Return_variable = helper(pre, 0, pre.length - 1, post, 0, post.length - 1);

return Return_variable;

}//function end

Utility Functions and Global variables:

private static TreeNode helper(int[] pre, int preStart, int preEnd, int[] post, int postStart, int postEnd) {

private TreeNode helper(int[] pre, int preStart, int preEnd, int[] post, int postStart, int postEnd) {

if (preStart > preEnd){

return null;

}//If End

TreeNode root = new TreeNode(pre[preStart]);

if (preStart == preEnd) {

return root;

}//If End

int leftRootVal = pre[preStart + 1];

int index = postStart;

while (post[index] != leftRootVal) {

index++;

}//Loop End

int leftSize = index - postStart + 1;

root.left = helper(pre, preStart + 1, preStart + leftSize, post, postStart, index);

root.right = helper(pre, preStart + leftSize + 1, preEnd, post, index + 1, postEnd - 1);