The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
869 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 _______;
    
    }
    
asked in DS by Veteran (59.5k points)
edited by | 869 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

3 Answers

+17 votes
Best answer

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;
    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

}
answered by Boss (17.5k points)
edited by
+2

This might help ..

+2

And this one ...

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?
+17 votes

ans for C :

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

$S2: return(1 + x)$

$S3: return(1 + y)$

answered by Loyal (8.2k points)
edited by
+12 votes

BST is:

answered by Loyal (8.2k points)
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


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,481 questions
46,655 answers
139,565 comments
57,349 users