Which or the following statements about a BST is NOT true? The value of any node

Question

Which or the following statements about a BST is NOT true? The value of any node in its left sub tree is less than the value of the node. The value of any node in its right sub tree is greater than the value of the node. A BST can have nodes with duplicate element. The minimum number of nodes in a BST can be zero. _ Which of the traversal methods has the root node visited first? Pre-order In-order Post-Order None _ For a BST with n nodes, on average how long will it take to find a specific node in the tree: n log(n) n n^2 log(n) _ The operation for inserting an entry on a Stack is traditionally called: add push pop top for the following big-Oh notation in terms of n, which runs the slowest: n log(n^2) log(log(n)) 2^n

Explanation / Answer

1)
Ans :- d
Explanation :- A tree is said to be binary search tree if the left subtree is less than the node and right subtree is greater than the node. This proves that the option a and b are true. A tree can have duplicate nodes as it doesn't violate the definition of BST. A tree is nothing but a graph which contains no loops , we should have atleast one node to say that its a graph. So the answer is 'D'.

2)
Ans :- a
Explanation :- Naming of the traversals are made based on the occurence of root node. If we are visiting the root node first , then it means it is preorder traversal. Because pre means before. So the answer is 'A'.

3)
Ans :- d
Explanation :- When we traverse through tree , for every step there will be 1/2 number of nodes gets decreased to be searched. So on average , the searching time is log(n). So the answer is 'D'.

4)
Ans :- b
Explanation :- We have traditional naming for doing operations for stack. For inserting we have 'push' operation.

5)
Ans :- d
Explanation :- 2^n is the answer for this question, because when we have big number of n , then the time to do that operation is very big than others. Simply we can find the answer by taking one number like 10 and calculating the value for all the options. Bigger value is the function that takes much time, which means it is slowest. So the answer is 'd' i.e.,2^n.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.