Using part A and B, Construct a binary search tree from a sorted list Problem 3:
ID: 3585874 • Letter: U
Question
Using part A and B, Construct a binary search tree from a sorted list
Problem 3: Constructing a Binary Search Tree from a Sorted List. (a) [10 points] Suppose you have elements with keys1.. , n. Write a recursive function insertAl(i, j) that inserts elements with keys ithrough j into a binary search tree so that the tree generated by insertAll(1,n) has height (gn (b) [5 points] Trace the execution of your function for the case where n 6, i.e., the initial call is insertAl(1, 6). Write down the sequence of recursive calls and draw what the tree looks like after each insertion.Explanation / Answer
a. Since no language is specified I'll be using C/C++. I'll be assuming that the start pointer of the tree is a global variable. The tree has the following structure using a linked list representation.
struct node {
struct node *lchild; //Points to the left child of the node
int data; //Data stored in the node
struct node *rchild; //Points to the right child of the node.
}
Since we are adding a sorted list in a BST it will always be a right skewed tree because the elements are always non decreasing.
void function(int i, int j)
{
struct node *tmp;
tmp=(struct node *) malloc(sizeof(struct node *)); //Allocating a node memory
tmp->data=i; //Assinging data
tmp->lchild=null; //Left child=null
tmp->rchild=null //Right child=null
struct node *q=start; //To find where to put the node
if(q==null)
start=tmp;
else
{
while(q->rchild!=null) //Traverse to the null pointer
q=q->rchild;
q->rchild=tmp;
}
if(i==j)
return
else
function(i+1,j)
}
b. After the first iteration i=1,j=6
1 -Start=1
Second iteration i=2,j=6
1
2 2 is added to the right child of 1 since 2 is bigger than 1
Similarly, Third iteration i=3,j=6
1
2
3
Fourth Iteration i=4,j=6
1
2
3
4
Fifth iteration i=5,j=6
1
2
3
4
5
Sixth iteration i=6,j=6 Since i==j so now return
1
2
3
4
5
6
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.