Binary Tree Basics: Understanding Children Count

Question 1

How many children does a binary tree have? 2 any number of children 0 or 1 or 2 0 or 1.

Question 2

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

Question 3

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

Question 4

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

Question 5

A binary tree is a rooted tree but not an ordered tree true false binary tree is a rooted tree but not an ordered tree binary tree is a rooted tree but not an ordered tree, Question 6 How many common operations are performed in a binary tree? 1 2 3 4

Question 7

What is the space complexity of the in-order traversal in the recursive fashion? (d is the tree depth and n is the number of nodes) O(1) O(nlogd) O(logd)

Question 8

In a full binary tree if number of internal nodes is I, then number of leaves L are? L =2*I L = I + 1 L = l - 1 L=2* I - 1

Question 9

What is a complete binary tree? Each node has exactly zero or two children A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from right to left A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right A tree In which all nodes have degree 2

Question 10

The number of edges from the root to the node is called ___ of the tree Height Depth Length Width

Question 11

Using what formula can a parent node be located in an array? (i+1)/2 (i-1)/2 i/2 2i/2

Question 12

If binary trees are represented in arrays, what formula can be used to locate a left child, if the node has an index i?2i+1 2i+2 2i 4i

Question 13

How many orders of traversal are applicable to a binary tree (In General)? 1 4 2 3

Question 14

How many types of insertion are performed in a binary tree? 1 2 3

Question 15

What is the traversal strategy used in the binary tree? depth-first traversal breadth-first traversal random traversal Priority traversal