GATE CSE 2004 | Question: 4, ISRO2009-26

Question

The following numbers are inserted into an empty binary search tree in the given order: $10, 1, 3, 5, 15, 12, 16$. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?

• A. $2$
• B. $3$
• C. $4$
• D. $6$

Answer 1

Height is 3

Correct Answer: $B$

Comments

Why are we not balancing the tree when the elements are inserted into the tree?

Won't it be a balanced binary search tree of height 2?

---

They didn't mention in the question, they are only saying use a empty binary search tree.

---

Root node is at height 0 or 1.nothing mentioned here,answer can be 3 or 4 depend upon that Or i am missing something?

---

It is clearly mentioned:

the height is the maximum distance of a leaf node from the root.

Therefore, count the edges from root to maximum height.

---

Its like finding distance between two nodes in graph. there are 3 hops to reach lowest leaf node. Also we can look it like there are 3 edges in betweeen.

---

Why We are not balancing tree at node one factor will -2 so after balancing height will result as 2 ???

---

they dint say that root is at height 0 right?? then how do you consider it

---

only height is asked not any other so wee need not to do it

---

They did not tell us to balance it. Balancing is carried out if it is mentioned that it is an AVL tree.

---

because they are not saying to balance , they have not even mentioned the word in thewhole question . in gate pyq the answer is “ only for exactly what is asked “

Answer 2

ans is (b)

Comments

what tool did you use bro to draw this ? Kinda curious

---

This https://www.cs.usfca.edu/~galles/visualization/BST.html

Answer 3

Ans) 3

Draw a BST for the given numbers And the Distance from root(i.e 10) to leaf(i.e 5) is 3.

Answer 4

ans will be 3 . hence option (b)