CPS02-Day3-NWC -Set02

What is the traversal strategy used in the binary tree?

• depth-first traversal
• breadth-first traversal
• random traversal
• Priority traversal

What are the children for node ‘w’ of a complete-binary tree in an array representation?

• 2w and 2w+1
• 2+w and 2-w
• w+1/2 and w/2
• w-1/2 and w+1/2

Consider a situation of writing a binary tree into a file with memory storage efficiency in mind, is array representation of tree is good?

• yes because we are overcoming the need of pointers and so space efficiency
• yes because array values are indexable
• No it is not efficient in case of sparse trees and remaning cases it is fine
• No linked list representation of tree is only fine

What is the parent for a node ‘w’ of a complete binary tree in an array representation when w is not 0?

• floor(w-1/2)
• ceil(w-1/2)
• w-1/2
• w/2

Can a tree stored in an array using either one of inorder or post order or pre order traversals be again reformed?

• Yes just traverse through the array and form the tree
• No we need one more traversal to form a tree
• No in case of sparse trees
• Yes by using both inorder and array elements

If the tree is not a complete binary tree then what changes can be made for easy access of children of a node in the array?

• every node stores data saying which of its children exist in the array
• no need of any changes continue with 2w and 2w+1, if node is at i
• keep a seperate table telling children of a node
• use another array parallel to the array with tree

How many children does a binary tree have?

• 2
• any number of children
• 0 or 1 or 2
• 0 or 1

What is/are the disadvantages of implementing tree using normal arrays?

• difficulty in knowing children nodes of a node
• difficult in finding the parent of a node
• have to know the maximum number of nodes possible before creation of trees
• difficult to implement

What must be the ideal size of array if the height of tree is ‘l’?

• 2l-1
• l-1
• l
• 2l

Level order traversal of a tree is formed with the help of

• breadth first search
• depth first search
• dijkstra’s algorithm
• prims algorithm