Utilizing Hash Map – O(n) Time and O(n) Space Pre-order Traversal
Though instead of linearly looking for every node in the in-order array, we can utilize hashing in line with first technique. Plot the indices of in-order arrays against their values. This will simplify searches from O(n) to O(1).
C++
// c++ program to construct tree using
// inorder and preorder traversals
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
Node(int x) {
data = x;
left = nullptr;
right = nullptr;
}
};
// Recursive function to build the binary tree.
Node* buildTreeRecur(unordered_map<int,int> &mp, vector<int>& pre,
int &preIndex, int s, int e) {
// For empty array, return null
if (s>e) return nullptr;
// create the root Node
Node* root = new Node(pre[preIndex]);
preIndex++;
// find the index of first element of pre-order array
// in the in-order array.
int index = mp[pre[preIndex-1]];
// Recursively create the left and right subtree.
root->left = buildTreeRecur(mp, pre, preIndex, s, index-1);
root->right = buildTreeRecur(mp, pre, preIndex, index+1, e);
return root;
}
Node* buildTree(vector<int>& in, vector<int>& pre) {
// Build the tree recursively.
int preIndex = 0;
int n = pre.size();
// Map the values to their indices
unordered_map<int,int> mp;
for (int i=0; i<n; i++) {
mp[in[i]] = i;
}
Node* root = buildTreeRecur
(mp, pre, preIndex, 0, n-1);
return root;
}
void printPostorder(Node* root) {
if (root == nullptr)
return;
printPostorder(root->left);
printPostorder(root->right);
cout << root->data << " ";
}
int main() {
vector<int> in = {3, 1, 4, 0, 5, 2};
vector<int> pre = {0, 1, 3, 4, 2, 5};
Node* root = buildTree(in, pre);
printPostorder(root);
return 0;
}Java
// Java program to construct tree using
// inorder and preorder traversals
import java.util.HashMap;
class Node {
int data;
Node left, right;
Node(int x) {
data = x;
left = null;
right = null;
}
}
class GfG {
// Recursive function to build the binary tree.
static Node buildTreeRecur(HashMap<Integer, Integer> map,
int[] pre, int[] preIndex, int s, int e) {
// For empty array, return null
if (s > e) return null;
// create the root Node
Node root = new Node(pre[preIndex[0]]);
preIndex[0]++;
// find the index of first element of pre-order array
// in the in-order array.
int index = map.get(pre[preIndex[0] - 1]);
// Recursively create the left and right subtree.
root.left = buildTreeRecur(map, pre, preIndex, s, index - 1);
root.right = buildTreeRecur(map, pre, preIndex, index + 1, e);
return root;
}
static Node buildTree(int[] in, int[] pre) {
int n = in.length;
// Build the tree recursively.
int[] preIndex = {0};
// Map the values to their indices
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
map.put(in[i], i);
}
return buildTreeRecur(map, pre, preIndex, 0, n - 1);
}
static void printPostorder(Node root) {
if (root == null)
return;
printPostorder(root.left);
printPostorder(root.right);
System.out.print(root.data + " ");
}
public static void main(String[] args) {
int[] in = {3, 1, 4, 0, 5, 2};
int[] pre = {0, 1, 3, 4, 2, 5};
Node root = buildTree(in, pre);
printPostorder(root);
}
}Python
# Python program to construct tree using
# inorder and preorder traversals
class Node:
def __init__(self, x):
self.data = x
self.left = None
self.right = None
# Recursive function to build the binary tree.
def buildTreeRecur(map, pre, preIndex, s, e):
# For empty array, return None
if s > e:
return None
# create the root Node
root = Node(pre[preIndex[0]])
preIndex[0] += 1
# find the index of first element of pre-order array
# in the in-order array.
index = map[pre[preIndex[0] - 1]]
# Recursively create the left and right subtree.
root.left = buildTreeRecur(map, pre, preIndex, s, index - 1)
root.right = buildTreeRecur(map, pre, preIndex, index + 1, e)
return root
def buildTree(inorder, preorder):
n = len(inorder)
# Build the tree recursively.
preIndex = [0]
# Map the values to their indices
map = {inorder[i]: i for i in range(n)}
return buildTreeRecur(map, preorder, preIndex, 0, n - 1)
def printPostorder(root):
if root is None:
return
printPostorder(root.left)
printPostorder(root.right)
print(root.data, end=" ")
inorder = [3, 1, 4, 0, 5, 2]
preorder = [0, 1, 3, 4, 2, 5]
root = buildTree(inorder, preorder)
printPostorder(root)C#
// C# program to construct tree using
// inorder and preorder traversals
using System;
using System.Collections.Generic;
class Node {
public int data;
public Node left, right;
public Node(int x) {
data = x;
left = null;
right = null;
}
}
class GfG {
// Recursive function to build the binary tree.
static Node BuildTreeRecur(Dictionary<int, int> map,
List<int> pre, ref int preIndex, int s, int e) {
// For empty array, return null
if (s > e) return null;
// create the root Node
Node root = new Node(pre[preIndex]);
preIndex++;
// find the index of first element of pre-order array
// in the in-order array.
int index = map[pre[preIndex - 1]];
// Recursively create the left and
// right subtree.
root.left = BuildTreeRecur(map, pre,
ref preIndex, s, index - 1);
root.right = BuildTreeRecur(map, pre,
ref preIndex, index + 1, e);
return root;
}
static Node BuildTree(List<int> inorder,
List<int> preorder) {
int n = inorder.Count;
// Build the tree recursively.
int preIndex = 0;
// Map the values to their indices
Dictionary<int, int> map = new Dictionary<int, int>();
for (int i = 0; i < n; i++) {
map[inorder[i]] = i;
}
return BuildTreeRecur(map, preorder,
ref preIndex, 0, n - 1);
}
static void PrintPostorder(Node root) {
if (root == null)
return;
PrintPostorder(root.left);
PrintPostorder(root.right);
Console.Write(root.data + " ");
}
static void Main() {
List<int> inorder = new List<int> { 3, 1, 4, 0, 5, 2 };
List<int> preorder = new List<int> { 0, 1, 3, 4, 2, 5 };
Node root = BuildTree(inorder, preorder);
PrintPostorder(root);
}
}Output
3 4 1 5 2 0