The question is below. You can write either the code or pseudocode. Let the Bina

ID: 3755437 • Letter: T

Question

 The question is below.  You can write either the code or pseudocode.

    Let the BinarySearchTree class be defined as follows:     class BinarySearchTree {         class Tree {                 int element;                  Tree left, right;                 Tree(int x, Tree l, Tree r) {                         element = x;                         left = l;                         right = r;                 }         }          Tree root;  // root of binary search tree         int size;   // number of elements in the BST          BinarySearchTree() {  // constructor                 root = null;                 size = 0;         }          BinarySearchTree(Tree t, int s) {  // constructor                 root = t;                 size = s;         }    }  1. Given a sorted array of integers, write an algorithm to build a height-balanced     binary search tree with its elements.  Analyze the running time of the algorithm.    Recursive algorithms can be solved using the Master method.     The functions that you need to write are the following.          // Build a height-balanced BST from arr[0..arr.length-1]         BinarySearchTree arrayToBST(int[] arr) { /* To do */ }          // Helper function to build a tree from a subarray         // Recursive algorithm that builds a tree recursively from the elements of arr[p..r].         // Returned tree is balanced, and satisfies the order constraints of a BST.         Tree arrayToTree(int[] arr, int p, int r) { /* To do */ }

Explanation / Answer

// Java program to print BST in given range

// A binary tree node

class Node {

int data;

Node left, right;

Node(int d) {

data = d;

left = right = null;

}

class BinaryTree {

static Node root;

/* A function that constructs Balanced Binary Search Tree

from a sorted array */

Node sortedArrayToBST(int arr[], int start, int end) {

/* Base Case */

if (start > end) {

return null;

}

/* Get the middle element and make it root */

int mid = (start + end) / 2;

Node node = new Node(arr[mid]);

/* Recursively construct the left subtree and make it

left child of root */

node.left = sortedArrayToBST(arr, start, mid - 1);

/* Recursively construct the right subtree and make it

right child of root */

node.right = sortedArrayToBST(arr, mid + 1, end);

return node;

}

/* A utility function to print preorder traversal of BST */

void preOrder(Node node) {

if (node == null) {

return;

}

System.out.print(node.data + " ");

preOrder(node.left);

preOrder(node.right);

}

public static void main(String[] args) {

BinaryTree tree = new BinaryTree();

int arr[] = new int[]{1, 2, 3, 4, 5, 6, 7};

int n = arr.length;

root = tree.sortedArrayToBST(arr, 0, n - 1);

System.out.println("Preorder traversal of constructed BST");

tree.preOrder(root);

}