Construct Tree From Given Inorder and Preorder traversals in C++

Construct Tree From Given Inorder and Preorder traversals in C++

There are three types of traversals in a tree: Inorder, Preorder and Postorder traversal. A tree can be formed with any two tree traversals in which one of them being the in order traversal.

Preorder Traversal: We first print the node, then move to the left subtree and the right subtree.

Inorder Traversal: We first move to the left subtree, then print the node and move to the right subtree.

Constructing a tree using given inorder and preorder in C++

Algorithm For InOrder Traversal:

  1. Traverse The Left subtree.
  2. Print the node.
  3. Traverse the right subtree.

Algorithm For PreOrder Traversal:

  1. Print the node.
  2. Traverse the left subtree.
  3. Traverse the right subtree.
Creating A tree using preorder and inorder

Algorithm To Create Tree:

  1. Pick the first element and increment the count.
  2. Find the position of the element in inorder traversal.
  3. Call recursively for the left subtree and make it as the left child of the current node.
  4. Call recursively for the right subtree and make it as the right child of the current node.

Code:

#include<bits/stdc++.h> 
using namespace std
class Tree {
    public:
        int data;
        Tree* left = NULL,*right = NULL;
        // Constructor initialised
        Tree(int x) {
            data = x;
            left = NULL;
            right = NULL;
        }
};
int search(int inorder[],int start,int end,int element) {
    for (int i = start; i < end;i++) {
        // Check whether same or not
        if (inorder[i] == element) {
            return i;
        }
    }
}
void printInorder(Tree* node
    if (node == NULL
        return
 
    // Call left subtree
    printInorder(node->left); 
 
    // Print data
    cout<<node->data<<” “
 
    // Call Right subtree
    printInorder(node->right); 
}
Tree* build_tree(int inorder[],int preorder[],int start,int end){
    static int index = 0;
    // Not possible
    if (start > end) return NULL;
    Tree* curr_node = new Tree(preorder[index++]);
    int x = curr_node -> data;
    if (start == end) // Return the current nod
        return curr_node; 
 
    int search_index = search(inorder, start, end,x ); 
    // Recursively call left subtree
    curr_node->left = build_tree(inorder, preorder, start, search_index – 1); 
    // Recursively call right subtree
    curr_node -> right = build_tree(inorder, preorder, search_index + 1, end); 
 
    return curr_node; 
}
int main() {
    int in[] = { 1225303740506062707587 }; 
    int pre[] = {5025123730407562607087  }; 
    Tree* root = build_tree(in, pre, 010); 
    cout << “Inorder traversal\n
    printInorder(root); 
    return 0;
}

Output:

Inorder traversal
12 25 30 37 40 50 60 62 70 75 87

 

Time Complexity To Build Tree using Preorder and Inorder

Time Complexity

O(n ^ 2) in worst case

Space Complexity

O(n)