1.2k 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;
if (t == NULL) return 0;
x = depth (t -> left);
S1:     ___________;

S2:     if (x > y) return __________;

S3:     else return _______;

}

edited | 1.2k views
+2
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 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
0
There is a subtle difference between the height of a node and depth of a node. But for a given binary tree, height and depth always return the same value.
0
Why depth is +1?
0
@Raghav? Where it is written like that?

what is depth of a node?

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?
+11
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