NIELIT 2016 DEC Scientist B (CS) - Section B: 15

Question

Which of the following need not be a binary tree?

• A. Search tree
• B. Heap
• C. AVL tree
• D. B tree

Comments

Heap need not be always binary , it may be $d_{ary}$ heap

---

A B-Tree is not a binary tree , it may be n-ary tree

---

(b) B-Tree

---

Heap needn't be a binary tree always. The only requirement to be a heap is it should be a complete tree.

---

@smsubham : your argument is valid $\text{iff}$ Heap is a $\text{binary heap}$

---

@ sourav. 

By mistake added binary in 2nd sentence. Check now.

Heap Variants:

• 2-3 heap
• Binary heap
• Many many others

---

The only requirement to be a heap is it should be a complete tree.

also $\text{Almost complete binary tree}$

---

What is the difference between complete and almost complete binary tree?

---

https://stackoverflow.com/questions/26327125/difference-between-complete-and-almost-complete-binary-tree

---

Saw that before asking, But things aren't clear there. Can you give an example which is complete BT but not almost complete BT and vice versa?

---

if last level of the tree are completely fill then it is complete binary tree 

and if 2nd last level are completely filled but the last level is not completely filled then it is almost complete binary tree

---

So definition and examples given here are wrong i suppose.

https://www.geeksforgeeks.org/binary-tree-set-3-types-of-binary-tree/

According to it: 

Complete Binary Tree: A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible

Following are examples of Complete Binary Trees

               18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40


               18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40
     /  \   /
    8   7  9 

---

first one is complete and other is almost complete  binary tree

---

If there is another option(e) Search Tree then can "Option (e) - Search Tree" also be an answer? Because search tree can be a "Ternary search tree" and need not to be binary.

---

What is the answer given..

is it both a and b

---

Option D

---

@haralk10 see my answer, even A and B are correct.

Answer 1

Will be both Heap and B tree.

Heaps

Definition: A heap is a specialized tree-based data structure that satisfied the heap property: if B is a child node of A, then key(A) ≥ key(B). This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap. Of course, there's also a min-heap. Variants: 2-3 heap Binary Heap Many many others Binary heap storage rules  -- A heap implemented with a binary tree in which the following two rules are followed: The element contained by each node is greater than or equal to the elements of that node's children. The tree is a complete binary tree.

So heap needn't be binary always.

AVL tree is BST with balancing factor.

Source: https://www.cpp.edu/~ftang/courses/CS241/notes/heap.htm

Comments

@smshubham : you are half correct.

you have wriiten that $\text{B tree}$ are not necessarily binary .It is correct.where is your explanation?

---

@sourav

The B-tree is a generalization of a binary search tree in that a node can have more than two children

Source: https://en.wikipedia.org/wiki/B-tree

Answer 2

B tree...................... B trees need not be the binary tree. B trees may have more than 2 children....

order of B tree is max. no. of children a node can have..

Comments

let me see a binary tree with more than 2 children!!!!

---

binary tree always have  2 children...but B trees need not be only 2 children it may have more than 2 children.....

---

@ Priyanka Agarwal  yes you are right

---

I don't think this is correct. Check my answer.

Answer 3

Search Tree => Can be Binary or n ary (Even B+ tree, AVL Tree are search tree only)

Heap => Can be binary as well as n ary

AVL Tree => Also a search tree, usually its binary. (didn't get any reference saying otherwise)

B Tree => Not necessarily a binary tree.

So A,B,D need not be a binary tree.

But in exam one can select D, as that maybe most appropriate "as per examiner".

Answer 4

B-Tree is the answer as it can bee m-ary .

heap is almost complete binary tree and AVL tree is height balanced binary tree.