Given 2 arrays, the first one containing postorder traversal sequence and the second one containing the information whether the corresponding node in the first array is a leaf node or a non-leaf node, create a binary tree and return its root and print it’s inorder traversal. (There can be more than one tree possible, but you have to form only one tree)
Examples:
Input:
postorder = {40, 20, 50, 60, 30, 10}
isLeaf = {true, false, true, true, false, false}
Output: 20 40 10 50 30 60
Explanation:
Generated Binary tree
10
/ \
20 30
\ / \
40 50 60
Input:
postorder = {20, 18, 25, 100, 81, 15, 7}
isLeaf = {true, false, true, true, false, false, false}
Output: 7 18 20 15 25 81 100
Explanation:
Generated Binary tree
7
\
15
/ \
18 81
\ / \
20 25 100
Approach:
The idea is to first construct the root node of the binary tree using the last key in the post-order sequence. Then using the given boolean array, we find if the root node is an internal node or a leaf node. If the root node is an internal node, we recursively construct its right and left subtrees.
Below is the implementation of the above approach :
C++
// C++ implementation for// the above approach#include <bits/stdc++.h>using namespace std;// struct to store // tree nodesstruct Tree { int val; Tree* leftchild; Tree* rightchild; Tree(int _val, Tree* _leftchild, Tree* _rightchild) { val = _val; leftchild = _leftchild; rightchild = _rightchild; }};// Function to generate binary tree // from given postorder traversal sequence// and leaf or non-leaf node information.struct Tree* createBinaryTree(int post[], bool isLeaf[], int& n){ // Base condition if (n < 0){ return NULL; } struct Tree* root = new Tree(post[n], NULL, NULL); bool isInternalNode = !isLeaf[n]; n--; // If internal node // creating left and // right child if (isInternalNode) { root->rightchild = createBinaryTree(post, isLeaf, n); root->leftchild = createBinaryTree(post, isLeaf, n); } return root;}// Function to print // in-order traversal // of a binary tree.void inorder(struct Tree* root){ if (root == NULL){ return; } inorder(root->leftchild); cout << root->val << " "; inorder(root->rightchild);}// Driver codeint main(){ int post[] = { 40, 20, 50, 60, 30, 10 }; bool isLeaf[] = { true, false, true, true, false, false }; int n = sizeof(post) / sizeof(post[0]) - 1; struct Tree* root = createBinaryTree(post, isLeaf, n); inorder(root); return 0;} |
Java
// Java implementation for// the above approachclass GFG{static int n;// to store tree nodesstatic class Tree{ int val; Tree leftchild; Tree rightchild; Tree(int _val, Tree _leftchild, Tree _rightchild) { val = _val; leftchild = _leftchild; rightchild = _rightchild; }};// Function to generate binary tree // from given postorder traversal sequence// and leaf or non-leaf node information.static Tree createBinaryTree(int post[], boolean isLeaf[]){ // Base condition if (n < 0) { return null; } Tree root = new Tree(post[n], null, null); boolean isInternalNode = !isLeaf[n]; n--; // If internal node creating left and // right child if (isInternalNode) { root.rightchild = createBinaryTree(post, isLeaf); root.leftchild = createBinaryTree(post, isLeaf); } return root;}// Function to print in-order traversal // of a binary tree.static void inorder(Tree root){ if (root == null) { return; } inorder(root.leftchild); System.out.print(root.val + " "); inorder(root.rightchild);}// Driver codepublic static void main(String[] args) { int post[] = { 40, 20, 50, 60, 30, 10 }; boolean isLeaf[] = { true, false, true, true, false, false }; n = post.length - 1; Tree root = createBinaryTree(post, isLeaf); inorder(root);}}// This code is contributed by Rajput-Ji |
Python3
# Python implementation of above algorithm# Utility class to create a node class Tree: def __init__(self, key): self.val = key self.leftchild = self.rightchild = Nonen = 0# Function to generate binary tree # from given postorder traversal sequence# and leaf or non-leaf node information.def createBinaryTree( post, isLeaf): global n # Base condition if (n < 0): return None root = Tree(post[n]) isInternalNode = not isLeaf[n] n = n - 1 # If internal node # creating left and # right child if (isInternalNode): root.rightchild = createBinaryTree(post, isLeaf) root.leftchild = createBinaryTree(post, isLeaf) return root# Function to print # in-order traversal # of a binary tree.def inorder( root): if (root == None): return inorder(root.leftchild) print( root.val ,end = " ") inorder(root.rightchild)# Driver codepost = [40, 20, 50, 60, 30, 10] isLeaf = [True, False, True, True, False, False ]n = len(post)-1root = createBinaryTree(post, isLeaf)inorder(root)# This code is contributed by Arnab Kundu |
C#
// C# implementation of the above approach using System; class GFG{static int n;// to store tree nodespublic class Tree{ public int val; public Tree leftchild; public Tree rightchild; public Tree(int _val, Tree _leftchild, Tree _rightchild) { val = _val; leftchild = _leftchild; rightchild = _rightchild; }};// Function to generate binary tree // from given postorder traversal sequence// and leaf or non-leaf node information.static Tree createBinaryTree(int []post, Boolean []isLeaf){ // Base condition if (n < 0) { return null; } Tree root = new Tree(post[n], null, null); Boolean isInternalNode = !isLeaf[n]; n--; // If internal node creating left and // right child if (isInternalNode) { root.rightchild = createBinaryTree(post, isLeaf); root.leftchild = createBinaryTree(post, isLeaf); } return root;}// Function to print in-order traversal // of a binary tree.static void inorder(Tree root){ if (root == null) { return; } inorder(root.leftchild); Console.Write(root.val + " "); inorder(root.rightchild);}// Driver codepublic static void Main(String[] args) { int []post = { 40, 20, 50, 60, 30, 10 }; Boolean []isLeaf = { true, false, true, true, false, false }; n = post.Length - 1; Tree root = createBinaryTree(post, isLeaf); inorder(root);}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// JavaScript implementation of the above approach var n;// to store tree nodesclass Tree{ constructor(_val, _leftchild, _rightchild) { this.val = _val; this.leftchild = _leftchild; this.rightchild = _rightchild; }};// Function to generate binary tree // from given postorder traversal sequence// and leaf or non-leaf node information.function createBinaryTree(post, isLeaf){ // Base condition if (n < 0) { return null; } var root = new Tree(post[n], null, null); var isInternalNode = !isLeaf[n]; n--; // If internal node creating left and // right child if (isInternalNode) { root.rightchild = createBinaryTree(post, isLeaf); root.leftchild = createBinaryTree(post, isLeaf); } return root;}// Function to print in-order traversal // of a binary tree.function inorder(root){ if (root == null) { return; } inorder(root.leftchild); document.write(root.val + " "); inorder(root.rightchild);}// Driver codevar post = [40, 20, 50, 60, 30, 10];var isLeaf = [true, false, true, true, false, false ];n = post.length - 1;var root = createBinaryTree(post, isLeaf);inorder(root);</script> |
Output:
20 40 10 50 30 60
Time Complexity: O(N).
Auxiliary Space: O(N).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
