This is not a programming assignment. Write code or pseudocode Let the BinarySea

Question

This is not a programming assignment. Write code or pseudocode Let the BinarySearchTree class be defined as follows: class BinarySearchTree f class Tree ( int element; Tree left, right; Tree (int x, Tree l, Tree r) I element -x; left = 1; 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*/h // Helper function to build a tree from a subarray // Recursive algorithm that builds a tree recursively from the elements of arrlp..r] // Returned tree is balanced, and satisfies the order constraints of a BST Tree arrayToTree (int[ arr, int p, int r) /* To do */ 2. Given a binary search tree of integers, and an integer x, write the functions floor and ceiling. Hint: If x is not in the tree, the floor and ceiling elements are on the path taken by find(x) // Class to store 2 integers class Pair { int floor, ceiling; Pair ( int f, int c) { floor = f; ceiling = c; } } // Floor: largest element of the BST that is less than or equal to x // Ceiling: smallest element of the BST that is greater than or equal to x Pair floorAndCeiling(BinarySearchTree t, int x) To do */ h

Explanation / Answer

Please find the solution to your question. Let me know if you have any concerns.

Answer Qn 1.

//Helper function to convert array to tree having a root.

Tree ArrayToTree(int arr[],int p, int r) {

  

int p = 0;

int r = arr.length-1;

if (p > r) { // Base Case

return null;

}

  

// Get the middle element and make it root

int mid = (p + r) / 2;

Tree t = new Tree();

t.left = null;

t.right = null;

Tree tree = new Tree(arr[mid],t.left,t.right);

return tree;

}

// Main Function

BinarySearchTree arrayToBst(int[] arr) {

Tree root = ArrayToTree(arr,0,arr.length-1);// Getting root of the bst

int p = 0;

int r = arr.length-1;

int mid = (p+r)/2;

// Recursively construct the left subtree and make it

// left child of root

root.left = ArrayToTree(arr, p, mid - 1);

  

// Recursively construct the right subtree and make it

//right child of root

root.right = ArrayToTree(arr, mid + 1, r);

BinarySearchTree bst = new BinarySearchTree(root,n);

return bst;// return the bst

}

Time complexity , T(n) = 2T(n/2) + C,where

T(n) is Time taken for an array of size n

C is a Constant for finding middle of array

Answer Qn 2.

Pair FloorAndCeeling(BinarySearchTree b, int x){

//Do the InorderOrder Traversal of the BinarySearchTree and store the elements of BST in

//array.

int[] a=InOrder(b);

// InOrder traversal of a BST inserts the elements in array in sorted Order.

//Traverse the array

for i= 0 <--a.length - 1

{if(a[i] == x)

floor = a[i-1];//by the defination

ceil= a[i+1];// by the defination

pair(floor,ceil);

}

return pair;

}

//Recursive function for Inorder Traversal

InOrder (BinarySearchTree b){

InOrder(b->leftSubtee);

InOrder(b->root);

InOrder(b->rightSubtree);

}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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