796 views
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;
it (t == NULL) return 0;
x = depth (t -> left);
S1:     ___________;

S2:     if (x > y) return __________;

S3:     else return _______;

}

edited | 796 views
+1
0
it should return -1 for proper depth when NULL encountered.As of now best we can get is levels with the given code
0
 it (t == NULL) return 0;
x = depth (t -> left);

some one correct it

Binary search tree will be:

After delete of root: use inorder predecessor

Or After delete of root: use inorder sucessor

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

int depth (Tree t)
{
int x, y;
it (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

}
selected by
+1

This might help ..

+2

And this one ...

ans for C :

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

$S2: return(1 + x)$

$S3: return(1 + y)$

edited by

BST is:

0
after deletion of root it will replace by it's successor, rt?but here u r replacing by predecessor. why?
+8
we can replace in both way inorder predecessor(largest element in left subtree) or inorder successor (smallest element in right subtree)  doesn't violate BST