Given a Binary Search Tree that is populated with numerical data, write an algor

Question

Given a Binary Search Tree that is populated with numerical data, write an algorithm that will determine the largest value in the tree that is less than the median of all the values in the tree.

Express your algorithm in Java-like pseudocode. You may use any of the operations supported by DJW's Binary Search Tree implementation (see BSTInterface.java).

Your solution must be developed at the application level.

Make sure you know what the median is.

If you use the operations in DJW's BSTInterface.java, please use numBST for the name of the BinarySearchTree object. Object instantiation and variable declarations are not needed. Do not include any logic in your solution that populates or changes the values in the tree.

Note: partial credit may be awarded for submissions that describe how to determine the median.

Explanation / Answer

1. Traversing a BST in INORDER witll print the tree in ascending order
2. If the number of nodes is odd, the middlw element will be the median and if the number of nodes is even then
   median is the average of two middle values.
3. In this case the largest node less than the median will be at (n/2)-1 location for odd n and for even n it will be n/2 location.

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

class BST{
     private Node root;
     public BST(int[] a){
         this();
         root = null;
         for (int i : a) {
             add(i);
         }
     }
     public void add(int item) {
        if (root == null) {
            root = new Node(null, item, null);
            return;
        }

        Node node = root;
        while (true) {
            if (item < node.item) {
                if (node.left == null) {
                    node.left = new Node(null, item, null);
                    break;
                }
                node = node.left;
            } else {
                if (node.right == null) {
                    node.right = new Node(null, item, null);
                    break;
                }
                node = node.right;
            }
        }
    }
    public void inorder(int[] array, int index)
    {
     if (root != NULL)
     {
         inorder(root.left);
         array[index++] = root.getData();
         inorder(root.right);
     }
    }

   
}

class Test{
     public static void main(String[] args)
     {
         int[] array;
         int index;
         int ans;
         Node root;
         int data[] = new int[10];
         data[10] = {10,20,30,40,50,60,71,80,90,91};

         BST bst = new BST(data);
         index = 0;
         bst.inorder(array,index)
         ans = index/2;
         System.out.println("Largest node smaller than median: " + array[ans]);  
          
     }
}

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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