Draw the BST where the data value at each node is an integer and the values are entered in the following order 36,22,10,44,42,16
,25,3,23,24 solution
1 answer:
Answer and Explanation:
A BST is the short form for Binary Search Tree. It is a special type of binary tree data structure in which nodes are arranged in a particular order such that;
i. the left subtree of a particular node should always contain nodes whose key values are less than that of the key value of the node itself.
ii. the right subtree of a particular node should always contain nodes whose key values are greater than that of the key value of the node itself.
iii. the right and left subtrees should also be a binary search tree.
For the given set of data:
36,22,10,44,42,16,25,3,23,24;
The equivalent binary search tree is attached to this response.
<em>As shown in the attachment:</em>
i. the first data value (36) is the root node value.
ii. the second value (22) is less than the root node value (36), therefore, 22 goes to the left of the root node.
iii. the third value is 10. This is less than 36 and then also less than 22, so 10 goes to the left of 22.
iv. the fourth value is 44. This is greater than the root node value (36), therefore, 44 goes to the right of the root node.
v. the fifth value is 42. This is greater than the root value (36) so it is going to be positioned somewhere at the right of the root node. But it is less than the value (44) of the direct right node of the root node. Therefore, 42 goes to the left of the direct right (44) of the root node.
vi. the sixth value is 16. This is less than the root node value (36). So it is going to be positioned somewhere at the left of the root node. It is also less than the value (22) of the direct left node of the root node. So it is going to be positioned somewhere at the left of the node with 22. But it is greater than the node with 10. Therefore, 16 is going to be to the right of the node with 10.
This trend continues until all data values have been rightly positioned.
<em>PS: A binary tree is a data structure in which each node cannot have more than two nodes directly attached to it.</em>
<em />
You might be interested in
Answer:
Following are the code to this question:
//import package
import java.util.*;
import java.text.*;
public class Main//defining a class
{
static final int t = 50;//defining an integer constant variable
static int[] ele = new int[t];//defining an array
static int tS = 0;//defining integer variable
static void initelements()//defining a static method
{
Random r= new Random();//creating Random class Object
for (int i = 0; i < t; i++)//use loop to add value in array
ele[i] = Math.abs(r.nextInt()) % 100;//add value in array
}
static public boolean isSorted()//defining a method isSorted
{
boolean x = true;//defining boolean variable
for (int i = 0; i < (t - 1); i++)//use for loop to count array values
if (ele[i] > ele[i + 1])//use if to compare array values
x = false;//use boolean variable to hold false value
return x;//return boolean value
}
static public void swap(int x1, int x2)//defining swap method
{
tS++;//increment variable value by 1
//performing swapping
int te = ele[x1];//defining te variable that holds array values
ele[x1] = ele[x2];//exchanging array values
ele[x2] = te;//holding te values
}
static public void disp()//defining a method disp
{
int v1;
DecimalFormat f = new DecimalFormat("00");//creating DecimalFormat class Object
System.out.println("The elements array is:");//print message
for (int i = 0; i <t; i++)//defining for loop
{
v1 = ele[i];//holding array value in v1 variable
if (((i + 1) % 10) == 0)//use if to check i value
System.out.println(f.format(v1));//print value
else//else block
System.out.print(f.format(v1) + " ");//print value
}
System.out.println();//print space
}
static int getMinimum(int st, int en)//defining a method getMinimum
{
int iMi = st;//defining variable that holds parameter value
for (int i = st + 1; i <= en; i++)//use for loop compare array value
if (ele[i] < ele[iMi])//compare array value
iMi = i;//use iMi to hold loop value
return iMi;//return iMi value
}
static void selectionSort()//defining a selectionSort method
{
int e = t - 1;//defining e variable that holds total array count value
for (int i = 0; i < e; i++)//use for loop to call swap method
swap(i, getMinimum(i, e));//calling the swap method
}
public static void main(String[] args)//defining main method
{
initelements();//calling initelements method
disp();//calling disp method
System.out.println("elements is sorted: " + isSorted());//calling is isSorted method with the message
System.out.println();//for space
selectionSort();//calling selectionSort method
System.out.println("No of swaps :" + tS);//print totalswap value with the message
disp();//calling disp method
System.out.println("elements is sorted: " + isSorted());//calling is isSorted method with the message
System.out.println();//for space
}
}
Output:
Please find the attached file.
Explanation:
In this code inside the Main class, 5 static methods "initelements, isSorted, swap, disp, getMinimum and selectionSort" is declared, in which the first method holds random values in arrays, in second array it sorts its values, in the third method it swap the array, in the disp method it shows array values.
In the "getMinimum and selectionSort" it sorts array values and inside the main method, it calls all methods and prints their values.
