The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+16 votes
599 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 _______;
    
    }
    
asked in DS by Veteran (68.8k points)
edited by | 599 views
it should return -1 for proper depth when NULL encountered.As of now best we can get is levels with the given code
 it (t == NULL) return 0;
    x = depth (t -> left);

some one correct it

3 Answers

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

}
answered by Veteran (11.2k points)
selected by

This might help ..

And this one ...

+17 votes

ans for C :

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

$S2: return(1 + x)$

$S3: return(1 + y)$

answered by Boss (8.4k points)
edited by
+12 votes

BST is:

answered by Boss (8.4k points)
after deletion of root it will replace by it's successor, rt?but here u r replacing by predecessor. why?
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

32,442 questions
39,188 answers
108,798 comments
36,561 users