Need help asap, answer must be in java. COP 3337 Final Exam-Page 5 of 10 3. (15

Question

Need help asap, answer must be in java.

COP 3337 Final Exam-Page 5 of 10 3. (15 points) Let BSTree be the following class which implemens the method public BSTree makeBS BST as its paramete T (intlj postorder) that gets the postorder teaversal of S nput parameter, reconstructs the tree and return it as its ontput parameter public class BSTree private Node root; public BSTree O root null: public BSTree makeBST (int] postorder) //your code here private class Node public Node left; public Node right; public int data;

Explanation / Answer

class BSTree
{
public class Node
{
int data;
Node left, right;
Node(int data)
{
this.data = data;
left = right = null;
}
}

public class Index
{
int postindex = 0;
}
  
  
// postIndex is used to keep track of index in
Node constructBT(int postOrder[], Index postIndex,int key, int min, int max, int size)
{
// Base case
if (postIndex.postindex < 0)
return null;

Node root = null;
if (key > min && key < max)
{

root = new Node(key);
postIndex.postindex = postIndex.postindex - 1;

if (postIndex.postindex > 0)
{

root.right = constructBT(postOrder, postIndex,
postOrder [postIndex.postindex],key, max, size);

root.left = constructBT(postOrder , postIndex,
postOrder [postIndex.postindex],min, key, size);
}
}
return root;
}

// function to construct BST from given postorder
Node constructTree(int postOrder [], int size)
{
Index index = new Index();
index.postindex = size - 1;
return constructBT(postOrder , index, postOrder [index.postindex],
Integer.MIN_VALUE, Integer.MAX_VALUE, size);
}

// function to print inorder traversal
void postOrderTraversal (Node node)
{
if (node == null)
return;
postOrderTraversal (node.left);
System.out.print(node.data + " ");
postOrderTraversal (node.right);
}

public static void main(String[] args)
{
BSTree tree = new BSTree();
int postOrder [] = new int[]{10, 700, 50, 500, 400, 100};
int size = postOrder .length;
Node root = tree.constructTree(postOrder , size);
System.out.println("Inorder traversal of the constructed tree are: ");
tree.postOrderTraversal (root);
}
}

Output:

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.