in DS edited by
3,806 views
27 votes
  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 _______;
    
    }
    
in DS edited by
3.8k views

6 Comments

5
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

0
How does this algo. counts depth of a binary tree? x counts no. left moves & y counts no. of right moves in a binary tree. Isn't it?
0
edited by

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

}

I know that *Tree is an alias for struct node. Assuming code given in question is correct Tree t creates a pointer t since it consists of a statement t → left which is a member access through a pointer.

I can’t understand how Tree t creates a pointer rather than a structure variable?

0
moved by

Anyone who’s struggling with height and depth of tree this link clearly explain all doubts…

 

height and depth of tree

1

Subscribe to GO Classes for GATE CSE 2022

3 Answers

28 votes
 
Best answer

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 by

8 Comments

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.
2
Why depth is +1?
0
@Raghav? Where it is written like that?

what is depth of a node?
0
The depth of the tree will be the number of edges from the root to the tree's farthest leaf node. We don't care about path any more when depth pops in. We just count how many edges between the targeting node and the root, ignoring directions. So why root is getting added.
1

@Gupta731 We should add a 1 as this is a recursive call. Unless we call depth(leaf->left) or depth(leaf->right), we should return to the caller by adding a 1, as there is one edge encountered. The comment 'one for root' is actually confusing.

1
  • The depth of a node is the number of edges from the node to the tree's root node.
    A root node will have a depth of 0.

  • The height of a node is the number of edges on the longest path from the node to a leaf.
    A leaf node will have a height of 0.

Properties of a tree:

  • The height of a tree would be the height of its root node,
    or equivalently, the depth of its deepest node 

       but the program given in answer calculates levels of the tree that is one more than max depth of tree. 

3
what I feel is for the correct implementation we should return -1 when we encounter NULL , so that it nullify the +1 factor.
1
Height of the tree
0
19 votes

ans for C :

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

$S2: return(1 + x)$

$S3: return(1 + y)$

edited by
15 votes

BST is:

2 Comments

after deletion of root it will replace by it's successor, rt?but here u r replacing by predecessor. why?
1
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
12

Related questions

Ask
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