TESTBOOK TEST SERIES

Question

HOW TO SOLVE IT?

Comments

cant we zoom in the pic ?

---

answer will be B)n-p (first node will be root in tree)

mention that p nodes in right subtree then n-p-1 element should be present in left subtree and position of root will be n-p-1+1 = n-p.

---

This is a gate Q i think..

Is the answer B?

In BST, the first number that is inserted decides where the other nodes will go. So the first node is the root node.

All the nodes in the left subtree is less than the root and right subtree nodes are all greater than the root.

It says that p nodes are there in the right subtree meaning the root is lesser than all the p nodes in the right subtree.

Let l₁l₂.......l_x ROOT r₁r₂.....r_p be the in-order travsersal of BST.

[l_i indicates a node in the left subtree of root and r_i is a node in the right subtree.]

count(l₁l₂.......l_x ROOT r₁r₂.....r_p) =n

means that the total no. of nodes starting from l₁ to r_p is n and r_p's rank is n.

count(l₁l₂.......l_x ROOT) = n-count(r₁r₂.....r_p)=n-p

means that the total no. of nodes starting from l₁ to  ROOT is n and ROOT's rank is (n-p).

Shortcut:

Let inorder traversal be 3,4,5,6,7,8,9 and p=2(let).

So root comes at after 2 elements from right i.e. 7 is the root. What is it's rank(index in inorder traversal)? (7-2)=5.