Size, Sum, Max, Min & Find in BST

FAQ

1. What will happen to a Binary Search Tree if we have two equal values in our “list” ?
Answer: The same element wull be treated as a greater one with parent and will be placed in right side of that node.

2. When the length of our list is even , which element to be picked up as a root node for a list ?
Answer: It depends upon the question .

3. Why inorder of BST is always sorted ?
Answer: Because the value less than the node is always in left part of the node and value greater than the node is always in right part of the node following bst algo. 

Hint

1. size()- faith  is that recursion will give us the number of nodes in both left as well as the right subtrees of a BST just add 1 in the sum for own.
2. sum()- traverse all the nodes to get the value of every node and add it to the total sum. 
3. max()-If there is a value > root node then it will be found only in the right subtree. 
4. min()- min value cannot be found in the right subtree as it contains greater values than the root node.

MCQ

1. The time complexity of for finding size and sum in BST is
  a) O(n)
  b) O(1)
  c) O(log n)
  d) O(nxn)
 
Answer: a) O(n) 

2. The time complexity of for finding max and min in BST is
  a) Average case - O(n) && Worst case - O(nxn) 
  b) Average case - O(log2n) && Worst case - O(1) 
  c) Average case - O(n) && Worst case - O(log2n)
  d) Average case - O(log2n) && Worst case - O(n)
 
Answer: d) Average case - O(log2n) && Worst case - O(n)

3. The space complexity of for finding max, min, size and sum in BST considering the recusrion space is
  a) Average case - O(1) && Worst case - O(n) 
  b) Average case - O(log2n) && Worst case - O(1) 
  c) Average case - O(n) && Worst case - O(log2n)
  d) Average case - O(log2n) && Worst case - O(n)
  
Answer: d) Average case - O(log2n) && Worst case - O(n)

4. What is the speciality about the inorder traversal of a binary search tree?
  a) It traverses in a deccreasing order
  b) It traverses in an increasing order
  c) It traverses in a random fashion
  d) It traverses based on priority of the node
  
 Answer: b) It traverses in an increasing order