Construct the binary tree in C++ – you are given two traversal sequences

Once In this tutorial, we will briefly discuss the pre-order and in-order traversal of a binary tree. We then go on to construct the binary tree from the two traversal sequences in C++.

Note:  To construct a tree from traversals, we need at least two of the traversals. With only one traversal sequence we cannot uniquely determine the tree.

Pre-Order Traversal

In this type of traversal, the route is Root->Left->Right. So we first see the root node, then all the left children and finally the right children.

Morris Preorder Tree Traversal in C++

In-Order Traversal

In-Order traversal follows the route Left->Root->Right. So we go from left to right, first the left children then it’s the root and finally the right children.

Morris Inorder Tree Traversal in C++

Illustrative Example

Given a tree:   

Pre-order Traversal – 1 2 4 5 6 3

In-Order Traversal – 4 2 5 1 6 3

Construct Tree from Pre-Order and In-Order Traversals in C++

Data Structures: Maintain a stack and a set

Algorithm:

1. Use Pre-Order to find the root of the tree.
2. Once we find the root node, from the elements on the left side of the root node for In-Order traversal, make the left subtree, right side make the right subtree.
3. Next, recursively select each element from the Pre-Order traversal and create left and right subtrees.

Example:

In-Order : D B E A F C  Pre-Order : A B D E C F G

Step 1:

Step 2:

 

Code:

#include<bits/stdc++.h> 
using namespace std; 

class Node 
{ 
  public: 
  int val; 
  Node* left; 
  Node* right; 
  Node(int x) { val = x; } 
}; 

set<Node*> s; 
stack<Node*> st; 

Node* buildTree(int preorder[], int inorder[],int n) 
{ 

  Node* root = NULL; 
  for (int pre = 0, in = 0; pre < n;) 
  { 

    Node* node = NULL; 
    do
    { 
      node = new Node(preorder[pre]); 
      if (root == NULL) 
      { 
        root = node; 
      } 
      if (st.size() > 0) 
      { 
        if (s.find(st.top()) != s.end()) 
        { 
          s.erase(st.top()); 
          st.top()->right = node; 
          st.pop(); 
        } 
        else
        { 
          st.top()->left = node; 
        } 
      } 
      st.push(node); 
    } while (preorder[pre++] != inorder[in] && pre < n); 

    node = NULL; 
    while (st.size() > 0 && in < n && 
        st.top()->val == inorder[in]) 
    { 
      node = st.top(); 
      st.pop(); 
      in++; 
    } 

    if (node != NULL) 
    { 
      s.insert(node); 
      st.push(node); 
    } 
  } 

  return root; 
} 

void printInorder(Node* node) 
{ 
  if (node == NULL) 
    return; 

  printInorder(node->left); 

  cout << node->val << " "; 

  printInorder(node->right); 
} 

int main() 
{ 
  int in[] = { 4,2,5,1,6,3,7 }; 

  int pre[] = { 1,2,4,5,3,6,7 }; 

  int len = sizeof(in)/sizeof(int); 

  Node *root = buildTree(pre, in, len); 

  printInorder(root); 
  return 0; 
}

Output :

In Order Traversal : 4,2,5,1,6,3,7

 

This was a short tutorial on how to construct a binary tree from two traversal sequences in C++. I hope you find this useful!

Also read Reverse Level Order Traversal of Binary Tree in C++