Create Preorder Using Postorder and Leaf Nodes Array

10 Sept 2024 | 4 min read

In input, there are two arrays that are given to us. One array is an integer array that represents postorder traversal of a binary tree, and the other array is a Boolean array that provides information about the leaf nodes. For every element in the postorder array, there is a corresponding Boolean value in the leaf nodes array. If the value in the Boolean array is true, then the given elements will comprise a leaf node in the binary tree; otherwise, it will not. Our task is to display the preorder traversal of the binary tree whose postorder traversal is given in the input. Note that there might be a possibility that multiple binary trees exist of the same postorder traversal. One has to consider any one of the binary trees and according to that preorder traversal has to be displayed on the console.

Example 1:

Input

postorder = { 140, 120, 150, 160, 130, 110, 170 }

isLeaf = { true, false, true, true, false, false, false }

Output: { 170, 110, 120, 140, 130, 150, 160 }

Approach

The concept is to first identify the root node of the binary tree with the help of the last key in the postorder sequence. Then with the help of the given Boolean array, we check whether the root node is a leaf node or an internal node. If the root node is an internal node, we recursively create its left and right subtrees. The following is the implementation of the mentioned approach.

FileName: CreatePreorder.java

Output:

For a tree whose post order traversal is: 
140 120 150 160 130 110 170  
 
The preorder traversal is: 
170 110 120 140 130 150 160

Complexity Analysis: The time complexity, as well as the space complexity of the program, is O(n), where n is the number of elements present in the preorder array.

Next TopicDisplay Leaf nodes from Preorder of a BST in Java

← prev next →