Question

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 the basis of the two input sequences –– inOrder and postOrder.

Helper methods are allowed.

Answer 1

PLEASE GIVE IT A THUMBS UP

nikhil@nikhil-Vostro-15-3568:-/Desktop/CODE$ javac A.java nikhil@nikhil-Vostro-15-3568:-/Desktop/CODES java A 8 5 9 7 1 12 2 4 11 3 nikhil@nikhil-Vostro-15-3568:-/Desktop/CODE$||

class BinaryTree {
int data;
BinaryTree left, right;

public BinaryTree(int data)
{
this.data = data;
left = right = null;
}
}
class Index {
int index;
}

class A {
static BinaryTree buildUtil(int inOrder[], int postOrder[], int inStrt,
int inEnd, Index pIndex)
{   
if (inStrt > inEnd)
return null;
BinaryTree node = new BinaryTree(postOrder[pIndex.index]);
(pIndex.index)--;
if (inStrt == inEnd)
return node;
int iIndex = search(inOrder, inStrt, inEnd, node.data);
node.right = buildUtil(inOrder, postOrder, iIndex + 1, inEnd, pIndex);
node.left = buildUtil(inOrder, postOrder, inStrt, iIndex - 1, pIndex);

return node;
}
static BinaryTree buildTree(int inOrder[], int postOrder[]){
int n = inOrder.length;
Index pIndex = new Index();
pIndex.index = n - 1;
return buildUtil(inOrder, postOrder, 0, n - 1, pIndex);
}

static int search(int arr[], int strt, int end, int value)
{
int i;
for (i = strt; i <= end; i++) {
if (arr[i] == value)
break;
}
return i;
}
static void print(BinaryTree node)
{
if (node == null)
return;
System.out.print(node.data + " ");
print(node.left);
print(node.right);
}

public static void main(String[] args)
{
int inOrder[] = new int[] { 9,5,1,7,2,12,8,4,3,11 };
int postOrder[] = new int[] { 9,1,2,12,7,5,3,11,4,8 };   
BinaryTree head = buildTree(inOrder, postOrder);   
print(head);
}
}

NM000 13 16 -/Desktop/CODE/A.java (CODE) - Sublime Text (UNREGISTERED) File Edit Selection Find View Goto Tools Project Preferences Help FOLDERS A.java demo.cpp class BinaryTree { CODE int data; html Binary Tree left, right; node_modules public BinaryTree(int data) cold.gif this data = data; left = right = null; A cool.gif <> index.html class Index { /* main.js int index; sun.png 15 class A { thun.png static BinaryTree buildutil(int inOrder[], int postorder[], int instrt, - warm.gif int in End, Index pIndex) zero.jpg if (inStrt > inEnd) return null; 1.jpg BinaryTree node = new BinaryTree(postOrder (pIndex. index]); (pIndex. index)--; /* A.java if (instrt = inEnd) 6 a.out return node; int iIndex = search(inOrder, instrt, inEnd, node.data); /* B.java node, right = buildUtil(inOrder, postorder, iIndex + 1, inEnd, pIndex); node. left = buildUtil(inOrder, postorder, instrt, iIndex - 1, pIndex); e code.txt return node; data_keyword.se date.dat static BinaryTree buildTree(int inOrder[], int postorder[]) { int n = inOrder. length; /* demo.c Index pIndex = new Index(); pIndex. index = n - 1; /* demo.cpp return buildUtil(inOrder, postorder, 0, n. 1, pIndex); demo.csv /* demo.py static int search(int arr[], int strt, int end, int value) /* demo.sh int i; for (i = strt; i <= end; i++) { /* file1.json if (arr[i] = value) break; /* file2.json return i; Line 64, Column 1 CANNO A AB Spaces: 2 Java

-/Desktop/CODE/A.java (CODE) - Sublime Text (UNREGISTERED) Tools Project Preferences Help File Edit Selection Find View Goto A.java X demo.cpp static BinaryTree buildTree(int inOrder[], int postorder[]) { int n = inOrder. length; Index pIndex = new Index(); pIndex. index = n - 1; return buildutil(inOrder, postorder, 0, n. 1, pIndex); static int search(int arr[], int strt, int end, int value) int i; for (i = strt; i <= end; i++) { if (arr[i] = value) break; return i; static void print(BinaryTree node) FOLDERS CODE html node_modules cold.gif A cool.gif <> index.html /* main.js sun.png thun.png - warm.gif zero.jpg 1.jpg /* A.java 6 a.out /* B.java E code.txt data_keyword.se date.dat /* demo.c /* demo.cpp demo.csv /* demo.py /* demo.sh /* file1.json /* file2.json if (node == null) return; System.out.print(node.data + " "); print(node. Left); print(node, right); public static void main(String[] args) int inOrder[] = new int[] { 9,5,1,7,2,12,8,4,3,11 }; int postOrder[] = new int[] { 9,1,2,12,7,5,3,11,4,8 }; Binary Tree head = buildTree(inOrder, postorder); print (head): Line 64, Column 1 Spaces: 2 Java