1-Write an efficient algorithm to construct a binary tree from given inorder and postorder traversals.(java only).
2- Apply your proposed algorithm in the previous point to construct the binary tree with the following traversals (java code only):
In order traversal: 9 8 6 1 2 5 4
Postorder traversal: 9 6 1 8 5 4 2
`Hey,
Note: If you have any queries related the answer please do comment. I would be very happy to resolve all your queries.
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;
// Data structure to store a Binary Tree node
class Node
{
int key;
Node left, right;
Node(int key) {
this.key = key;
}
}
public class Main
{
// Recursive function to perform inorder traversal of
a binary tree
public static void inorderTraversal(Node root)
{
if (root == null) {
return;
}
inorderTraversal(root.left);
System.out.print(root.key + "
");
inorderTraversal(root.right);
}
// Recursive function to perform postorder
traversal of a binary tree
public static void postorderTraversal(Node root)
{
if (root == null) {
return;
}
postorderTraversal(root.left);
postorderTraversal(root.right);
System.out.print(root.key + "
");
}
// Recursive function to perform
postorder traversal of a binary tree
public static void preorderTraversal(Node root)
{
if (root == null) {
return;
}
System.out.print(root.key + "
");
postorderTraversal(root.left);
postorderTraversal(root.right);
}
// Recursive function to construct a binary tree
from
// inorder and postorder traversals
public static Node construct(int start, int end,
int[] postorder, AtomicInteger pIndex,
Map<Integer,Integer> map)
{
// base case
if (start > end) {
return
null;
}
// Consider the next item from
the end of given postorder sequence
// This value would be the root
node of subtree formed by inorder[start, end]
Node root = new
Node(postorder[pIndex.getAndDecrement()]);
// search the index of current
node in inorder sequence to determine
// the boundary of left and right
subtree
int index = map.get(root.key);
// recursively construct the
right subtree
root.right = construct(index + 1,
end, postorder, pIndex, map);
// recursively construct the
left subtree
root.left = construct(start, index
- 1, postorder, pIndex, map);
// return root node
return root;
}
// Construct a binary tree from inorder and
postorder traversals
// This function assumes that the input is valid
// i.e. given inorder and postorder sequence forms a
binary tree
public static Node construct(int[] inorder, int[]
postorder)
{
// get size
int n = inorder.length;
// map is used to efficiently
find the index of any element in
// given inorder sequence
Map<Integer,Integer> map =
new HashMap<>();
for (int i = 0; i < n; i++)
{
map.put(inorder[i], i);
}
// pIndex stores the index of
next unprocessed node from the end
// of postorder sequence
AtomicInteger pIndex = new
AtomicInteger(n - 1);
return construct(0, n - 1,
postorder, pIndex, map);
}
public static void main(String[] args)
{
int[] inorder = { 9,8,6,1,2,5,4
};
int[] postorder = { 9,6,1,8,5,4,2
};
Node root = construct(inorder, postorder);
// traverse the constructed
tree
System.out.print("Inorder : ");
inorderTraversal(root);
System.out.print("\nPostorder : ");
postorderTraversal(root);
System.out.print("\nPreorder : ");
preorderTraversal(root);
}
}
Note: Brother According to Chegg's policy we are only allowed to answer 1 part if it is not a one word answer and there are many. So, I request you to post other part as separate posts
Kindly revert for any queries
Thanks.
1-Write an efficient algorithm to construct a binary tree from given inorder and postorder traversals.(java only)....
There are generally considered to be four distinct binary tree traversals: preorder, inorder, postorder and level-order. Consider the following questions about these different kinds of traversals. Answer one of them that has not already been answered. What is the result of the various tree traversals when performed on an arithmetic expression tree? Which of the traversals are depth-first? Which are breadth-first? Which kind of traversal of a binary search tree produces the values in sorted order? Which of the traversals...
[Python] Construct Tree Using Inorder and Preorder Given Preorder and Inorder traversal of a binary tree, create the binary tree associated with the traversals.You just need to construct the tree and return the root. Note: Assume binary tree contains only unique elements. Input format : Line 1 : n (Total number of nodes in binary tree) Line 2 : Pre order traversal Line 3 : Inorder Traversal Output Format : Elements are printed level wise, each level in new line...
JAVA Given the sequence of in-order traversal for a general binary tree, stored in an array inOrder[] = {9, 5, 1, 7, 2, 12, 8, 4, 3, 11 }. And given the sequence of post-order traversal for the same tree, stored in an array postOrder[] = {9, 1, 2, 12, 7, 5, 3, 11, 4, 8}. Please implement the following method: static BinaryTree buildTree(Object inOrder[], Object postOrder[]) -The method buildTree() returns a BinaryTree object in memory that is constructed on...
Assume you are given “preorder” and “inorder” traversal result of a Binary Tree. Write an algorithm (pseudocode) that constructs the Binary Tree. For example, you can start with the Pre-Order and In-Order traversal of the same tree given below. Pre-Order = 80, 50, 10, 70, 100 In-Order = 10, 50, 70, 80, 100
Trees Traversals Please write a Java program to traverse a binary tree in in-order and pre-order, and to plot a binary tree into a 2-dimensional array. You may write many recursive methods for this project. You are not allowed to use any existing Java classes such as ArrayList or Vector or Tree. Please stop your program if the user enters 0 as the tree selection. Your program must run the following Test Case 1 plus two more test cases to...
QUESTION 4 The shape of binary tree is unknown (unrelated to the tree defined in problem 3). However, we do have the following information: performing an inorder and a postorder traversals of the tree (containing nine integer nodes with integer values from 1 through 9) yield the following outputs: a) Inorder (LNR): 123456789 b) Postorder (LRN): 1354 2 8 796 Based on the above traversal information, determine the shape of the binary tree. Note that there is no need to...
1) Write a java program to create a tree and apply the preorder, in-order and postorder traversal of the data items of the tree
Trees Traversals Please write a Java program to traverse a binary tree in in-order and pre-order, and to plot a binary tree into a 2-dimensional array. You may write many recursive methods for this project. You are not allowed to use any existing Java classes such as ArrayList or Vector or Tree. Please stop your program if the user enters 0 as the tree selection. Your program must run the following Test Case 1 plus two more test cases to...
Q8 - Construct a Binary Search Tree by inserting the following sequence of numbers. 5,6,3,2,10,4,1,7,9,8. Write down the level ordered traversal sequence of the final tree after insert. Delete node 10, 8, and 6 step by step using in-order successor. Write down the level ordered traversal sequence after every delete. I want you to write down (1 level ordered traversal for the insert and 3 level-ordered traversals for the deletes). In total there should be 4 level-ordered traversal sequences in...
a) Create a binary search tree with the 4 2 2 0 1 4 5 9 7 1 5 3 6 number. b) Provide the Preorder, Inorder and Postorder traversal of tree obtained in part (a). Show all the steps.