Home » Data Structure

Construct a Binary Tree from Postorder and Inorder Traversal

Here, we are going to see how we can construct a Binary Tree from Postorder and Inorder Traversal?
Submitted by Nikunj Nimesh, on February 19, 2020

Problem Statement:

Given the postorder and inorder traversals of a Binary Tree, using these traversals we have to create a binary tree.

Input:

Size of the postorder array N then add N more elements and store in the array, then enter the size of the inorder array M and add M more elements and store in the array.

Output:

Display the tree using the Display function.

Functions used in program:

  • findIndex(): function to find the index of a particular element in the array, if not found then return -1.
  • CreateTreefromPostIn(): function used to create tree using postOrder and inorder.
  • print(): function to display the tree.

Algorithm:

  1. Firstly call node*CreateTreefromPostIn(int post[], int in[], int pstart, int pend, int istart, int iend) function where post[] is postOrder array and in[] is inorder array and pstart, istart are starting indices of the post and in array and pend, iend are ending indices of post and in the array.
  2. In the CreateTreePostIn(), make the last element of the postOrder array as root node as in the postOrder traversal the last element is always the root of the tree,
  3. Now find out the index of that last element in the inorder array and as soon as that element is found out in the inorder array then make recursive call for all the elements to the left of root element in inorder array as they will be in left subtree and do the same for right subtree i.e. for elements after root element in inorder array.
  4. This createTreePostIn() will work until the pstart(starting index of postOrder array) is greater than or equal to pend(ending index of the inorder array).
  5. In the print the tree with the help of the display/print function using the root node returned by CreateTreePostIn() function.

Example with explanation:

    N=3
    PostOrder array:1 3 2

    M=3
    Inorder array: 1 2 3

    Now considering the above-mentioned input, 
    here the last element in postOrder is 2 so find 2 in the inorder array, 
    after this 1 is before 2 in the inorder array 
    so it will be in the left subtree, and 3 will be in the right subtree 
    and the root of the tree will be 2.

C++ Implementation:

#include <iostream>

using namespace std;
struct node {
  int data;
  node * left;
  node * right;
  node(int data) {
    this -> data = data;
    left = NULL;
    right = NULL;
  }
};

// function to determine the index of a particular element in the array
int findIndex(int v[], int data, int start, int end) {
  for (int i = start; i <= end; i++) {
    if (v[i] == data) {
      return i;
    }

  }
  return -1;
}
node * createTreeFromPostIn(int post[], int in [], int pstart, int pend, int istart, int iend) {
  if (pstart > pend) {
    return NULL;
  }

  node * root = new node(post[pend]);
  int index = findIndex( in , post[pend], istart, iend);
  int len = index - istart;
  root -> left = createTreeFromPostIn(post, in , pstart, pstart + len - 1, istart, index - 1);
  root -> right = createTreeFromPostIn(post, in , pstart + len, pend - 1, index + 1, iend);

  return root;
}

void print(node * root) {
  if (!root)
    return;
  if (root -> left)
    cout << root -> left -> data << " => ";
  else
    cout << "END => ";
  cout << root -> data << " <= ";
  if (root -> right)
    cout << root -> right -> data << endl;
  else
    cout << "END" << endl;
  print(root -> left);
  print(root -> right);
  return;
}

int main() {
  int n;
  cout<<"Enter postorder array size: ";
  //postorder array size
  cin >> n;
  int a[1000000]; //postorder array
  cout<<"\nEnter postorder array elements: ";
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  int m; //inorder array size
  cout<<"\nEnter inorder array size: ";
  int b[100]; //inorder array

  cin >> m;
  cout<<"\nEnter inorder array elements: ";
  for (int i = 0; i < n; i++) {
    cin >> b[i];
  }

  //root of the builded tree
  node * root = createTreeFromPostIn(a, b, 0, n - 1, 0, m - 1);
  cout<<endl<<"Builded Tree\n";
  print(root); //printing the tree
  
  return 0;
}

Output

Enter postorder array size: 3

Enter postorder array elements: 1 3 2 

Enter inorder array size: 3 

Enter inorder array elements: 1 2 3 

Builded Tree
1 => 2 <= 3 
END => 1 <= END 
END => 3 <= END





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.