edited by
6,788 views
33 votes
33 votes
  1. Insert the following keys one by one into a binary search tree in the order specified.$$15, 32, 20, 9, 3, 25, 12, 1$$Show the final binary search tree after the insertions.
  2. Draw the binary search tree after deleting $15$ from it.
  3. Complete the statements $S1$, $S2$ and $S3$ in the following function so that the function computes the depth of a binary tree rooted at $t$.
    typedef struct tnode{
        int key;
        struct tnode *left, *right;
    } *Tree;
    
    int depth (Tree t)
    {
        int x, y;
        if (t == NULL) return 0;
        x = depth (t -> left);
    S1:     ___________;
    
    S2:     if (x > y) return __________;
    
    S3:     else return _______;
    
    }
    
edited by

3 Answers

Best answer
32 votes
32 votes

Binary search tree will be$:$

 

After delete of root: use inorder predecessor

 

Or After delete of root: use inorder successor

 

typedef struct tnode{
    int key;
    struct tnode *left, *right;
} *Tree;

int depth (Tree t)
{
    int x, y;
    if (t == NULL) return 0;
    x = depth (t -> left);
S1: y = depth (t -> right);

S2:     if (x > y) return (1+x);one for root

S3:     else return (1+y); one for root

}
edited by
20 votes
20 votes

ans for C :

$S1: y = depth( t \rightarrow right )$

$S2: return(1 + x)$

$S3: return(1 + y)$

edited by
15 votes
15 votes

BST is:

Related questions

7 votes
7 votes
3 answers
2
go_editor asked Feb 8, 2018
1,986 views
Consider a relation examinee (regno, name, score), where regno is the primary key to score is a real number.Write an SQL query to list the regno of examinees who have a s...