Question

Here is a picture of a Binary Search Tree.



First, construct the Binary Search Tree using the following BinaryNode as we discussed in class.

public class BinaryNode {
        private int value;
        private BinaryNode leftChild;
        private BinaryNode rightChild;

        public BinaryNode(int value) {
                this.value = value;
                leftChild = null;
                rightChild = null;
        }

        public BinaryNode(int value, BinaryNode leftChild, BinaryNode rightChild)
        {
                this.value = value;
                this.leftChild = leftChild;
                this.rightChild = rightChild;
        }

        public int getValue() {
                return value;
        }

        public void setValue(int value) {
                this.value = value;
        }

        public BinaryNode getLeftChild() {
                return leftChild;
        }

        public void setLeftChild(BinaryNode leftChild) {
                this.leftChild = leftChild;
        }

        public BinaryNode getRightChild() {
                return rightChild;
        }

        public void setRightChild(BinaryNode rightChild) {
                this.rightChild = rightChild;
        }

        @Override
        public String toString() {
                return "BinaryNode: " +
                                "value=" + value;
        }
}

Second, print the nodes in level order, that is, the root node first, then the children of the root node, then the grand-children, etc. It is recommended that you accomplish this by using a queue to store the nodes, printing the first nodes that have been added to the queue.

Your program should print the following when it runs.

42 27 50 21 38 60 33 41 72

Submit the file LevelOrder.java when done.

Answer 1

//BinaryNode.java

public class BinaryNode {
        private int value;
        private BinaryNode leftChild;
        private BinaryNode rightChild;

        public BinaryNode(int value) {
                this.value = value;
                leftChild = null;
                rightChild = null;
        }

        public BinaryNode(int value, BinaryNode leftChild, BinaryNode rightChild)
        {
                this.value = value;
                this.leftChild = leftChild;
                this.rightChild = rightChild;
        }

        public int getValue() {
                return value;
        }

        public void setValue(int value) {
                this.value = value;
        }

        public BinaryNode getLeftChild() {
                return leftChild;
        }

        public void setLeftChild(BinaryNode leftChild) {
                this.leftChild = leftChild;
        }

        public BinaryNode getRightChild() {
                return rightChild;
        }

        public void setRightChild(BinaryNode rightChild) {
                this.rightChild = rightChild;
        }

        @Override
        public String toString() {
                return "BinaryNode: " +
                                "value=" + value;
        }
}

//BinarySearchTree.java

public class BinarySearchTree{
   private BinaryNode root;
  
   public BinarySearchTree() {
       root = null;
   }
  
   private BinaryNode insert(BinaryNode root,int data) {
       if(root==null)return new BinaryNode(data,null,null);
       if(root.getValue()>data)
           root.setLeftChild(insert(root.getLeftChild(),data));
      
       if(root.getValue() < data)
           root.setRightChild(insert(root.getRightChild(),data));
       return root;
   }
  
   public void insert(int data) {
       root = insert(root , data);
   }
  
   public void levelOrder() {
        if (root == null)
          return;
  
        Queue<BinaryNode> queue = new LinkedList<>();
        queue.add(root);
        queue.add(null);
        while (!queue.isEmpty()) {
  
          BinaryNode curr = queue.poll();
          if (curr == null) {
            if (!queue.isEmpty()) {
              queue.add(null);
            }
          } else {
            if (curr.getLeftChild() != null)
              queue.add(curr.getLeftChild());
  
            if (curr.getRightChild() != null)
              queue.add(curr.getRightChild());
  
            System.out.print(curr.getValue() + " ");
          }
        }
      }
}

//LevelOrder.java

import java.util.LinkedList;
import java.util.Queue;

public class LevelOrder {
   public static void main(String arg[]) {
       //42 27 50 21 38 60 33 41 72
       BinarySearchTree bst = new BinarySearchTree();
       bst.insert(42);
       bst.insert(27);
       bst.insert(50);
       bst.insert(21);
       bst.insert(38);
       bst.insert(60);
       bst.insert(33);
       bst.insert(41);
       bst.insert(72);
      
       bst.levelOrder();
   }
}