(IN JAVA) Binary search trees have their best performance when they are balanced
ID: 3572082 • Letter: #
Question
(IN JAVA)
Binary search trees have their best performance when they are balanced, which means that at each node n, the size of the left subtree of n is within one of the size of the right subtree of n. Write a static method that takes a sorted array of integers and produces a balanced binary search tree. (The array is sorted with smallest integers at the front and largest at the end.)
If useful, you can add extra parameters to the method, such can as the total number of entries in the list. Hint: First build the left subtree of the root, then the right subtree of the root, then put the pieces together with the join method from Self-Test Exercise 19 on page 513.
As an alternative, you can have the integer data come from a java vector rather than an array.
Explanation / Answer
Hi, please find my implementation.
Please let me know in case of any issue.
class TreeNode{
int data;
TreeNode left;
TreeNode right;
public TreeNode(int d) {
data = d;
left = null;
right = null;
}
}
TreeNode createMinimalBST(int arr[], int start, int end) {
if(end < start){
return null;
}
int mid = (start + end)/2;
TreeNode n = new TreeNode(arr[mid]);
n.left = createMinimalBST(arr, start, mid-1);
n.right = createMinimalBST(arr, mid+1, end);
return n;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.