The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+18 votes
730 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 (59.4k points)
edited by | 730 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

3 Answers

+12 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 Boss (16.6k points)
selected by
+1

This might help ..

+2

And this one ...

+17 votes

ans for C :

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

$S2: return(1 + x)$

$S3: return(1 + y)$

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

BST is:

answered by Loyal (8.3k 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

34,942 questions
41,955 answers
119,194 comments
41,471 users