3,806 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 _______;

}

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

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?
edited

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?

moved by

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

height and depth of tree

### Subscribe to GO Classes for GATE CSE 2022

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

}
by

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

what is depth of a node?
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.

@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.

• 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.

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

ans for C :

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

$S2: return(1 + x)$

$S3: return(1 + y)$

by

BST is:

by

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