123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109
#include <bits/stdc++.h>
using namespace std;
// TreeNode structure
struct TreeNode {
int data;
TreeNode *left;
TreeNode *right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
class Solution {
public:
// Function to build a binary tree
// from preorder and inorder traversals
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
// Create a map to store indices
// of elements in the inorder traversal
unordered_map<int, int> inMap;
// Populate the map with indices
// of elements in the inorder traversal
for (int i = 0; i < inorder.size(); i++) {
inMap[inorder[i]] = i;
}
// Call the private helper function
// to recursively build the tree
return buildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, inMap);
}
private:
// Recursive helper function to build the tree
TreeNode* buildTree(vector<int>& preorder, int preStart, int preEnd,
vector<int>& inorder, int inStart, int inEnd, unordered_map<int, int>& inMap) {
// Base case: If the start indices
// exceed the end indices, return null
if (preStart > preEnd || inStart > inEnd) {
return nullptr;
}
// Create a new TreeNode with value
// at the current preorder index
TreeNode* root = new TreeNode(preorder[preStart]);
// Find the index of the current root
// value in the inorder traversal
int inRoot = inMap[root->data];
// Calculate the number of
// elements in the left subtree
int numsLeft = inRoot - inStart;
// Recursively build the left subtree
root->left = buildTree(preorder, preStart + 1, preStart + numsLeft,
inorder, inStart, inRoot - 1, inMap);
// Recursively build the right subtree
root->right = buildTree(preorder, preStart + numsLeft + 1, preEnd,
inorder, inRoot + 1, inEnd, inMap);
// Return the current root node
return root;
}
// Function to print the
// inorder traversal of a tree
void printInorder(TreeNode* root) {
if (root != nullptr) {
printInorder(root->left);
cout << root->data << " ";
printInorder(root->right);
}
}
// Function to print the
// given vector
void printVector(vector<int>& vec) {
for (int i = 0; i < vec.size(); i++) {
cout << vec[i] << " ";
}
cout << endl;
}
public:
void run() {
vector<int> inorder = {9, 3, 15, 20, 7};
vector<int> preorder = {3, 9, 20, 15, 7};
cout << "Inorder Vector: ";
printVector(inorder);
cout << "Preorder Vector: ";
printVector(preorder);
TreeNode* root = buildTree(preorder, inorder);
cout << "Inorder of Unique Binary Tree Created:" << endl;
printInorder(root);
cout << endl;
}
};
int main() {
Solution sol;
sol.run();
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106
// Definition for a binary tree node.
public class TreeNode {
int data;
TreeNode left;
TreeNode right;
TreeNode(int val) {
data = val;
left = null;
right = null;
}
}
class Solution {
// Function to build a binary tree
// from preorder and inorder traversals
public TreeNode buildTree(int[] preorder, int[] inorder) {
// Create a map to store indices
// of elements in the inorder traversal
Map<Integer, Integer> inMap = new HashMap<>();
// Populate the map with indices
// of elements in the inorder traversal
for (int i = 0; i < inorder.length; i++) {
inMap.put(inorder[i], i);
}
// Call the private helper function
// to recursively build the tree
TreeNode root = buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inMap);
return root;
}
// Recursive helper function to build the tree
private TreeNode buildTree(int[] preorder, int preStart, int preEnd,
int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inMap) {
// Base case: If the start indices
// exceed the end indices, return null
if (preStart > preEnd || inStart > inEnd) {
return null;
}
// Create a new TreeNode with value
// at the current preorder index
TreeNode root = new TreeNode(preorder[preStart]);
// Find the index of the current root
// value in the inorder traversal
int inRoot = inMap.get(root.data);
// Calculate the number of
// elements in the left subtree
int numsLeft = inRoot - inStart;
// Recursively build the left subtree
root.left = buildTree(preorder, preStart + 1, preStart + numsLeft,
inorder, inStart, inRoot - 1, inMap);
// Recursively build the right subtree
root.right = buildTree(preorder, preStart + numsLeft + 1, preEnd,
inorder, inRoot + 1, inEnd, inMap);
// Return the current root node
return root;
}
// Function to print the
// inorder traversal of a tree
private void printInorder(TreeNode root) {
if (root != null) {
printInorder(root.left);
System.out.print(root.data + " ");
printInorder(root.right);
}
}
// Function to print the
// given array
private void printArray(int[] arr) {
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] inorder = {9, 3, 15, 20, 7};
int[] preorder = {3, 9, 20, 15, 7};
Solution sol = new Solution();
System.out.print("Inorder Array: ");
sol.printArray(inorder);
System.out.print("Preorder Array: ");
sol.printArray(preorder);
TreeNode root = sol.buildTree(preorder, inorder);
System.out.println("Inorder of Unique Binary Tree Created:");
sol.printInorder(root);
System.out.println();
}
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.data = val
self.left = left
self.right = right
class Solution:
def buildTree(self, preorder, inorder):
# Create a map to store indices
# of elements in the inorder traversal
inMap = {val: idx for idx, val in enumerate(inorder)}
# Recursive helper function to build the tree
def helper(preStart, preEnd, inStart, inEnd):
# Base case: If the start indices
# exceed the end indices, return null
if preStart > preEnd or inStart > inEnd:
return None
# Create a new TreeNode with value
# at the current preorder index
root_val = preorder[preStart]
root = TreeNode(root_val)
# Find the index of the current root
# value in the inorder traversal
inRoot = inMap[root_val]
# Calculate the number of
# elements in the left subtree
numsLeft = inRoot - inStart
# Recursively build the left subtree
root.left = helper(preStart + 1, preStart + numsLeft, inStart, inRoot - 1)
# Recursively build the right subtree
root.right = helper(preStart + numsLeft + 1, preEnd, inRoot + 1, inEnd)
# Return the current root node
return root
# Call the helper function to build the tree
return helper(0, len(preorder) - 1, 0, len(inorder) - 1)
# Function to print the
# inorder traversal of a tree
def printInorder(self, root):
if root:
self.printInorder(root.left)
print(root.data, end=" ")
self.printInorder(root.right)
# Function to print the
# given list
def printList(self, lst):
print(" ".join(map(str, lst)))
if __name__ == "__main__":
inorder = [9, 3, 15, 20, 7]
preorder = [3, 9, 20, 15, 7]
sol = Solution()
print("Inorder List: ", end="")
sol.printList(inorder)
print("Preorder List: ", end="")
sol.printList(preorder)
root = sol.buildTree(preorder, inorder)
print("Inorder of Unique Binary Tree Created:")
sol.printInorder(root)
print()
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485
// Definition for a binary tree node.
class TreeNode {
constructor(val = 0, left = null, right = null) {
this.data = val;
this.left = left;
this.right = right;
}
}
class Solution {
buildTree(preorder, inorder) {
// Create a map to store indices
// of elements in the inorder traversal
const inMap = new Map();
inorder.forEach((val, idx) => inMap.set(val, idx));
// Recursive helper function to build the tree
const build = (preStart, preEnd, inStart, inEnd) => {
// Base case: If the start indices
// exceed the end indices, return null
if (preStart > preEnd || inStart > inEnd) {
return null;
}
// Create a new TreeNode with value
// at the current preorder index
const rootVal = preorder[preStart];
const root = new TreeNode(rootVal);
// Find the index of the current root
// value in the inorder traversal
const inRoot = inMap.get(rootVal);
// Calculate the number of
// elements in the left subtree
const numsLeft = inRoot - inStart;
// Recursively build the left subtree
root.left = build(preStart + 1, preStart + numsLeft, inStart, inRoot - 1);
// Recursively build the right subtree
root.right = build(preStart + numsLeft + 1, preEnd, inRoot + 1, inEnd);
// Return the current root node
return root;
};
// Call the helper function to build the tree
return build(0, preorder.length - 1, 0, inorder.length - 1);
}
// Function to print the
// inorder traversal of a tree
printInorder(root) {
if (root) {
this.printInorder(root.left);
process.stdout.write(root.data + " ");
this.printInorder(root.right);
}
}
// Function to print the
// given array
printArray(arr) {
console.log(arr.join(" "));
}
}
const inorder = [9, 3, 15, 20, 7];
const preorder = [3, 9, 20, 15, 7];
const sol = new Solution();
console.log("Inorder Array: ");
sol.printArray(inorder);
console.log("Preorder Array: ");
sol.printArray(preorder);
const root = sol.buildTree(preorder, inorder);
console.log("Inorder of Unique Binary Tree Created:");
sol.printInorder(root);
console.log();
