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:
- Use Pre-Order to find the root of the tree.
- 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.
- 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++
Leave a Reply