Data structure interview questions Part 4

Data structure interview question:What is the bucket size, when the overlapping and collision occur at same time?

Answer:One. If there is only one entry possible in the bucket, when the collision occurs, there is no way to accommodate the colliding value. This results in the overlapping of values.

Data structure interview question: Traverse the given tree using Inorder, Preorder and Postorder traversals.

Answer:

Ø Inorder : D H B E A F C I G J

Ø Preorder: A B D H E C F G I J

Ø Postorder: H D E B F I J G C A

Data structure interview question:There are 8, 15, 13, 14 nodes were there in 4 different trees. Which of them could have formed a full binary tree?

Answer:15. 

In general:

There are 2n-1 nodes in a full binary tree.

By the method of elimination:

Full binary trees contain odd number of nodes. So there cannot be full binary trees with 8 or 14 nodes, so rejected. With 13 nodes you can form a complete binary tree but not a full binary tree. So the correct answer is 15.

Note:

Full and Complete binary trees are different. All full binary trees are complete binary trees but not vice versa.

Data structure interview question: In the given binary tree, using array you can store the node 4 at which location?

Answer:Left: 2i

Right:2i+1

i=location

At location  6

1

2

3

-

-

4

-

-

5

                       

Root

LC1

RC1

LC2

RC2

LC3

RC3

LC4

RC4

where LCn means Left Child of node n and RCn means Right Child  of node n.