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 imp 07/26/18 lements Binary Search Tree. Write Tree makeBST (intl postorder) that gets the postorder traversal of a put parameter, reconstructs the tree and return it as its output parameter public class BSTree private Node root public BSTree O1 root null; public BSTree makeBST (int]l postorder) //your code here private class Node ( public Node left; public Node right; public int daa;

Explanation / Answer

public class BSTree{
   private Node root;
   public BSTree() {
   root=null;
   }

public ArrayList<Integer> postorderTraversal(TreeNode root) {

        ArrayList<Integer> lst = new ArrayList<Integer>();

        if(root == null)
            return lst;

        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);

        TreeNode prev = null;
        while(!stack.empty()){
            TreeNode curr = stack.peek();

            // go down the tree.
            //check if current node is leaf, if so, process it and pop stack,
            //otherwise, keep going down
            if(prev == null || prev.left == curr || prev.right == curr){
                //prev == null is the situation for the root node
                if(curr.left != null){
                    stack.push(curr.left);
                }else if(curr.right != null){
                    stack.push(curr.right);
                }else{
                    stack.pop();
                    lst.add(curr.val);
                }

            //go up the tree from left node  
            //need to check if there is a right child
            //if yes, push it to stack
            //otherwise, process parent and pop stack
            }else if(curr.left == prev){
                if(curr.right != null){
                    stack.push(curr.right);
                }else{
                    stack.pop();
                    lst.add(curr.val);
                }

            //go up the tree from right node
            //after coming back from right node, process parent node and pop stack.
            }else if(curr.right == prev){
                stack.pop();
                lst.add(curr.val);
            }

            prev = curr;
        }

        return lst;
  
    private class Node{
      public Node left;
      public Node rihht;
      public int data;
}

    }

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

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