184 + Interview Questions in Binary Trees in Data Structures & Algorithms I Page 4 InterviewSolution

151.	For a binary tree the first node visited in in-order and post-order traversal is same.(a) True(b) FalseMy question is taken from Binary Trees topic in portion Binary Trees of Data Structures & Algorithms IThis question was addressed to me during an internship interview.
Answer» The correct option is (b) False The explanation is: Consider a BINARY tree, Its in-order TRAVERSAL – 13 14 16 19 Its post-order traversal- 14 13 19 16. Here the first node VISITED is not same.

Discussion

152.	The pre-order and in-order are traversals of a binary tree are T M L N P O Q and L M N T O P Q. Which of following is post-order traversal of the tree?(a) L N M O Q P T(b) N M O P O L T(c) L M N O P Q T(d) O P L M N Q TMy question comes from Binary Trees in chapter Binary Trees of Data Structures & Algorithms IThe question was asked during an internship interview.
Answer» The correct answer is (a) L N M O Q P T The EXPLANATION is: The tree generated by using GIVEN pre-order and in-order traversal is Thus, L N M O Q P T will be the post-order traversal.

Discussion

153.	The steps for finding post-order traversal are traverse the right subtree, traverse the left subtree or visit the current node.(a) True(b) FalseMy question is based upon Binary Trees topic in section Binary Trees of Data Structures & Algorithms IThe question was asked by my school principal while I was bunking the class.
Answer» RIGHT CHOICE is (b) False Explanation: Left subtree is TRAVERSED first in post-order traversal, then the right subtree is traversed and then the output CURRENT node.

Discussion

154.	The maximum number of nodes in a tree for which post-order and pre-order traversals may be equal is ______(a) 3(b) 1(c) 2(d) any numberThis key question is from Binary Trees topic in portion Binary Trees of Data Structures & Algorithms IThe question was asked in an online quiz.
Answer» CORRECT ANSWER is (B) 1 For EXPLANATION: The tree with only one node has post-order and pre-order traversals equal.

Discussion

155.	A full binary tree can be generated using ______(a) post-order and pre-order traversal(b) pre-order traversal(c) post-order traversal(d) in-order traversalThe origin of the question is Binary Trees in chapter Binary Trees of Data Structures & Algorithms IThe question was posed to me by my school principal while I was bunking the class.
Answer» Right choice is (a) post-order and pre-order traversal The explanation is: Every NODE in a full binary tree has either 0 or 2 children. A binary tree can be generated by TWO traversals if one of them is in-order. But, we can GENERATE a full binary tree USING post-order and pre-order traversals.

Discussion

156.	Which of the following pair’s traversals on a binary tree can build the tree uniquely?(a) post-order and pre-order(b) post-order and in-order(c) post-order and level order(d) level order and preorderThe query is from Binary Trees topic in portion Binary Trees of Data Structures & Algorithms IThe question was asked in class test.
Answer» Right answer is (B) post-order and in-order Best EXPLANATION: A binary tree can uniquely be CREATED by post-order and in-order traversals.

Discussion

157.	A binary search tree contains values 7, 8, 13, 26, 35, 40, 70, 75. Which one of the following is a valid post-order sequence of the tree provided the pre-order sequence as 35, 13, 7, 8, 26, 70, 40 and 75?(a) 7, 8, 26, 13, 75, 40, 70, 35(b) 26, 13, 7, 8, 70, 75, 40, 35(c) 7, 8, 13, 26, 35, 40, 70, 75(d) 8, 7, 26, 13, 40, 75, 70, 35I'm obligated to ask this question of Binary Trees in portion Binary Trees of Data Structures & Algorithms II have been asked this question in an online interview.
Answer» Correct choice is (d) 8, 7, 26, 13, 40, 75, 70, 35 For explanation: The binary TREE contains values 7, 8, 13, 26, 35, 40, 70, 75. The GIVEN pre-order sequence is 35, 13, 7, 8, 26, 70, 40 and 75. So, the binary search tree formed is Thus post-order sequence for the tree is 8, 7, 26, 13, 40, 75, 70 and 35.

Discussion

158.	The post-order traversal of a binary tree is O P Q R S T. Then possible pre-order traversal will be ________(a) T Q R S O P(b) T O Q R P S(c) T Q O P S R(d) T Q O S P RThis interesting question is from Binary Trees topic in division Binary Trees of Data Structures & Algorithms II have been asked this question by my school principal while I was bunking the class.
Answer» Correct answer is (C) T Q O P S R For explanation: The last, second last nodes visited in post-order TRAVERSAL are root and it’s right CHILD respectively. Option T Q R S O P can’t be a pre-order traversal, because nodes O, P are visited after the nodes Q, R, S. Option T O Q R P S, can’t be valid, because the pre-order sequence GIVEN in option T O Q R P Sand given post-order traversal creates a tree with node T as root and node O as left subtree. Option T Q O P S R is valid. Option T Q O S P R is not valid as node P is visited after VISITING node S.

Discussion

159.	What is the possible number of binary trees that can be created with 3 nodes, giving the sequence N, M, L when traversed in post-order.(a) 15(b) 3(c) 5(d) 8The query is from Binary Trees topic in chapter Binary Trees of Data Structures & Algorithms IThe question was asked in exam.
Answer» Right option is (c) 5 The EXPLANATION is: 5 BINARY trees are POSSIBLE and they are,

Discussion

160.	In postorder traversal of binary tree right subtree is traversed before visiting root.(a) True(b) FalseMy question comes from Binary Trees in chapter Binary Trees of Data Structures & Algorithms II had been asked this question in unit test.
Answer» RIGHT choice is (a) True Easiest EXPLANATION - Post-order method of TRAVERSING involves– i) TRAVERSE left subtree in post-order, ii) Traverse right subtree in post-order, III) visit the root.

Discussion

161.	Which of the following properties are obeyed by all three tree – traversals?(a) Left subtrees are visited before right subtrees(b) Right subtrees are visited before left subtrees(c) Root node is visited before left subtree(d) Root node is visited before right subtreeMy question is from Binary Trees topic in chapter Binary Trees of Data Structures & Algorithms IThis question was addressed to me during an online exam.
Answer» RIGHT ANSWER is (a) Left subtrees are visited before right subtrees Best explanation: In preorder, INORDER and postorder traversal the left subtrees are visited before the right subtrees. In Inorder traversal, the Left subtree is visited first then the Root NODE then the Right subtree. In postorder traversal, the Left subtree is visited first, then Right subtree and then the Root node is visited.

Discussion

162.	Using what formula can a parent node be located in an array?(a) (i+1)/2(b) (i-1)/2(c) i/2(d) 2i/2The query is from Binary Trees in chapter Binary Trees of Data Structures & Algorithms IThis question was addressed to me during an interview for a job.
Answer» The CORRECT answer is (B) (i-1)/2 Easy explanation - If a binary tree is represented in an array, PARENT nodes are found at INDICES (i-1)/2.

Discussion

163.	If binary trees are represented in arrays, what formula can be used to locate a left child, if the node has an index i?(a) 2i+1(b) 2i+2(c) 2i(d) 4iQuestion is taken from Binary Trees topic in division Binary Trees of Data Structures & Algorithms II got this question during an internship interview.
Answer» The correct option is (a) 2i+1 Easiest explanation - If binary TREES are REPRESENTED in ARRAYS, LEFT CHILDREN are located at indices 2i+1 and right children at 2i+2.

Discussion

164.	How many orders of traversal are applicable to a binary tree (In General)?(a) 1(b) 4(c) 2(d) 3The question is from Binary Trees in section Binary Trees of Data Structures & Algorithms II had been asked this question in an interview for internship.
Answer» Right option is (d) 3 To explain: The three orders of TRAVERSAL that can be applied to a BINARY TREE are in-ORDER, pre-order and post order traversal.

Discussion

165.	The average depth of a binary tree is given as?(a) O(N)(b) O(√N)(c) O(N^2)(d) O(log N)My query is from Binary Trees topic in chapter Binary Trees of Data Structures & Algorithms IThe question was asked in semester exam.
Answer» CORRECT OPTION is (d) O(log N) The BEST I can explain: The average depth of a binary tree is given as O(√N). In CASE of a binary search tree, it is O(log N).

Discussion

166.	How many bits would a succinct binary tree occupy?(a) n+O(n)(b) 2n+O(n)(c) n/2(d) nMy question is from Binary Trees topic in division Binary Trees of Data Structures & Algorithms IThe question was asked in unit test.
Answer» Correct option is (b) 2n+O(n) The best I can explain: A SUCCINCT binary tree OCCUPIES CLOSE to minimum POSSIBLE space established by lower BOUNDS. A succinct binary tree would occupy 2n+O(n) bits.

Discussion

167.	General ordered tree can be encoded into binary trees.(a) true(b) falseAsked question is from Binary Trees in portion Binary Trees of Data Structures & Algorithms II have been asked this question by my school teacher while I was bunking the class.
Answer» RIGHT answer is (a) true Easiest EXPLANATION - General ordered TREE can be mapped into binary tree by representing them in a left-child-right-sibling WAY.

Discussion

168.	What operation does the following diagram depict?(a) inserting a leaf node(b) inserting an internal node(c) deleting a node with 0 or 1 child(d) deleting a node with 2 childrenThis interesting question is from Binary Trees in section Binary Trees of Data Structures & Algorithms IThe question was asked during an internship interview.
Answer» The CORRECT choice is (C) deleting a node with 0 or 1 CHILD The best EXPLANATION: The above DIAGRAM is a depiction of deleting a node with 0 or 1 child since the node D which has 1 child is deleted.

Discussion

169.	How many types of insertion are performed in a binary tree?(a) 1(b) 2(c) 3(d) 4Query is from Binary Trees topic in division Binary Trees of Data Structures & Algorithms IThe question was posed to me in an internship interview.
Answer» Right choice is (B) 2 Explanation: TWO KINDS of INSERTION operation is performed in a binary tree- inserting a LEAF node and inserting an internal node.

Discussion

170.	What is the traversal strategy used in the binary tree?(a) depth-first traversal(b) breadth-first traversal(c) random traversal(d) Priority traversalAsked question is from Binary Trees topic in section Binary Trees of Data Structures & Algorithms IThe question was posed to me by my college professor while I was bunking the class.
Answer» Correct answer is (b) breadth-first TRAVERSAL For explanation: Breadth first traversal, ALSO known as LEVEL order traversal is the traversal strategy used in a binary tree. It INVOLVES visiting all the nodes at a GIVEN level.

Discussion

171.	How many common operations are performed in a binary tree?(a) 1(b) 2(c) 3(d) 4This intriguing question comes from Binary Trees topic in division Binary Trees of Data Structures & Algorithms IThe question was posed to me during an online exam.
Answer» Correct choice is (c) 3 Explanation: Three common operations are performed in a BINARY TREE- they are INSERTION, deletion and TRAVERSAL.

Discussion

172.	A binary tree is a rooted tree but not an ordered tree.(a) true(b) falseI need to ask this question from Binary Trees topic in division Binary Trees of Data Structures & Algorithms IThis question was addressed to me during an interview.
Answer» Right answer is (b) false Easy explanation - A binary tree is a rooted tree and also an ordered tree (i.e) EVERY NODE in a binary tree has at most two CHILDREN.

Discussion

173.	The following given tree is an example for?(a) Binary tree(b) Binary search tree(c) Fibonacci tree(d) AVL treeMy question is from Binary Trees topic in section Binary Trees of Data Structures & Algorithms IThe question was posed to me in a national level competition.
Answer» Correct option is (a) BINARY TREE Easiest explanation - The given tree is an example for binary tree since has got two children and the LEFT and right children do not satisfy binary SEARCH tree’s property, Fibonacci and AVL tree.

Discussion

174.	What is the maximum number of children that a binary tree node can have?(a) 0(b) 1(c) 2(d) 3This intriguing question comes from Binary Trees topic in section Binary Trees of Data Structures & Algorithms IThe question was posed to me in exam.
Answer» Right OPTION is (C) 2 Best explanation: In a binary tree, a NODE can have atmost 2 NODES (i.e.) 0,1 or 2 left and right child.

Discussion

175.	What may be the psuedo code for finding the size of a tree?(a) find_size(root_node–>left_node) + 1 + find_size(root_node–>right_node)(b) find_size(root_node–>left_node) + find_size(root_node–>right_node)(c) find_size(root_node–>right_node) – 1(d) find_size(root_node–>left_node + 1The above asked question is from Binary Trees using Linked Lists in chapter Binary Trees of Data Structures & Algorithms IThis question was posed to me in a job interview.
Answer» CORRECT choice is (a) find_size(root_node–>left_node) + 1 + find_size(root_node–>right_node) Easy explanation - Draw a tree and analyze the expression. we are always taking size of left subtree and right subtree and adding root VALUE(1) to it and FINALLY PRINTING size.

Discussion

176.	The following lines talks about deleting a node in a binary tree.(the tree property must not be violated after deletion)i) from root search for the node to be deletedii)iii) delete the node atwhat must be statement ii) and fill up statement iii)(a) ii)-find random node,replace with node to be deleted. iii)- delete the node(b) ii)-find node to be deleted. iii)- delete the node at found location(c) ii)-find deepest node,replace with node to be deleted. iii)- delete a node(d) ii)-find deepest node,replace with node to be deleted. iii)- delete the deepest nodeEnquiry is from Binary Trees using Linked Lists in chapter Binary Trees of Data Structures & Algorithms IThe question was asked during an online interview.
Answer» The correct option is (d) ii)-find deepest node,REPLACE with node to be DELETED. III)- DELETE the deepest node Easiest explanation - We just replace a to be deleted node with last leaf node of a TREE. this must not be done in case of BST or heaps.

Discussion

177.	Identify the reason which doesn’t play a key role to use threaded binary trees?(a) The storage required by stack and queue is more(b) The pointers in most of nodes of a binary tree are NULL(c) It is Difficult to find a successor node(d) They occupy less sizeQuestion is taken from Binary Trees using Linked Lists in section Binary Trees of Data Structures & Algorithms II got this question in exam.
Answer» Right choice is (d) They occupy less SIZE Easiest explanation - Threaded binary trees are INTRODUCED to make the Inorder traversal faster without USING any stack or recursion. Stack and QUEUE require more SPACE and pointers in the majority of binary trees are null and difficulties are raised while finding successor nodes. Size constraints are not taken on threaded binary trees, but they occupy less space than a stack/queue.

Discussion

178.	Level order traversal of a tree is formed with the help of(a) breadth first search(b) depth first search(c) dijkstra’s algorithm(d) prims algorithmMy question is based upon Binary Trees using Linked Lists in portion Binary Trees of Data Structures & Algorithms IThis question was addressed to me in an interview for job.
Answer» Correct OPTION is (a) BREADTH FIRST search The best explanation: LEVEL order is similar to bfs.

Discussion

179.	Which of the following traversing algorithm is not used to traverse in a tree?(a) Post order(b) Pre order(c) Post order(d) RandomizedQuestion is taken from Binary Trees using Linked Lists in division Binary Trees of Data Structures & Algorithms IThe question was posed to me in an interview for job.
Answer» Right answer is (d) Randomized To EXPLAIN: Generally, all nodes in a tree are visited by using PREORDER, inorder and postorder TRAVERSING algorithms.

Discussion

180.	Disadvantages of linked list representation of binary trees over arrays?(a) Randomly accessing is not possible(b) Extra memory for a pointer is needed with every element in the list(c) Difficulty in deletion(d) Random access is not possible and extra memory with every elementI need to ask this question from Binary Trees using Linked Lists in section Binary Trees of Data Structures & Algorithms II had been asked this question in a job interview.
Answer» RIGHT option is (d) Random ACCESS is not POSSIBLE and extra MEMORY with every element Easy explanation - Random access is not possible with linked LISTS.

Discussion

181.	Advantages of linked list representation of binary trees over arrays?(a) dynamic size(b) ease of insertion/deletion(c) ease in randomly accessing a node(d) both dynamic size and ease in insertion/deletionThis interesting question is from Binary Trees using Linked Lists in division Binary Trees of Data Structures & Algorithms II got this question in my homework.
Answer» Right option is (d) both DYNAMIC size and ease in INSERTION/DELETION The best I can explain: It has both dynamic size and ease in insertion and deletion as advantages.

Discussion

182.	Can a tree stored in an array using either one of inorder or post order or pre order traversals be again reformed?(a) Yes just traverse through the array and form the tree(b) No we need one more traversal to form a tree(c) No in case of sparse trees(d) Yes by using both inorder and array elementsMy doubt is from Binary Trees using Array topic in section Binary Trees of Data Structures & Algorithms II had been asked this question by my school principal while I was bunking the class.
Answer» Correct choice is (b) No we need one more traversal to form a tree For EXPLANATION: We need any two traversals for tree formation but if some additional STUFF or TECHNIQUES are used while storing a tree in an array then one traversal can FACILITATE like also storing null VALUES of a node in array.

Discussion

183.	What is/are the disadvantages of implementing tree using normal arrays?(a) difficulty in knowing children nodes of a node(b) difficult in finding the parent of a node(c) have to know the maximum number of nodes possible before creation of trees(d) difficult to implementThis intriguing question comes from Binary Trees using Array in division Binary Trees of Data Structures & Algorithms II have been asked this question in quiz.
Answer» CORRECT option is (c) have to know the maximum number of nodes possible before creation of TREES The explanation is: The size of array is fixed in normal ARRAYS. We need to know the number of nodes in the tree before array declaration. It is the main DISADVANTAGE of using arrays to represent binary trees.

Discussion

184.	How many children does a binary tree have?(a) 2(b) any number of children(c) 0 or 1 or 2(d) 0 or 1The above asked question is from Binary Trees using Array topic in division Binary Trees of Data Structures & Algorithms II had been asked this question during an interview for a job.
Answer» Correct choice is (c) 0 or 1 or 2 Best explanation: Can have ATMOST 2 NODES.

Discussion

Explore topic-wise InterviewSolutions in .

For a binary tree the first node visited in in-order and post-order traversal is same.(a) True(b) FalseMy question is taken from Binary Trees topic in portion Binary Trees of Data Structures & Algorithms IThis question was addressed to me during an internship interview.

The maximum number of nodes in a tree for which post-order and pre-order traversals may be equal is ______(a) 3(b) 1(c) 2(d) any numberThis key question is from Binary Trees topic in portion Binary Trees of Data Structures & Algorithms IThe question was asked in an online quiz.

What is the possible number of binary trees that can be created with 3 nodes, giving the sequence N, M, L when traversed in post-order.(a) 15(b) 3(c) 5(d) 8The query is from Binary Trees topic in chapter Binary Trees of Data Structures & Algorithms IThe question was asked in exam.

In postorder traversal of binary tree right subtree is traversed before visiting root.(a) True(b) FalseMy question comes from Binary Trees in chapter Binary Trees of Data Structures & Algorithms II had been asked this question in unit test.

Using what formula can a parent node be located in an array?(a) (i+1)/2(b) (i-1)/2(c) i/2(d) 2i/2The query is from Binary Trees in chapter Binary Trees of Data Structures & Algorithms IThis question was addressed to me during an interview for a job.

If binary trees are represented in arrays, what formula can be used to locate a left child, if the node has an index i?(a) 2i+1(b) 2i+2(c) 2i(d) 4iQuestion is taken from Binary Trees topic in division Binary Trees of Data Structures & Algorithms II got this question during an internship interview.

How many orders of traversal are applicable to a binary tree (In General)?(a) 1(b) 4(c) 2(d) 3The question is from Binary Trees in section Binary Trees of Data Structures & Algorithms II had been asked this question in an interview for internship.

The average depth of a binary tree is given as?(a) O(N)(b) O(√N)(c) O(N^2)(d) O(log N)My query is from Binary Trees topic in chapter Binary Trees of Data Structures & Algorithms IThe question was asked in semester exam.

How many bits would a succinct binary tree occupy?(a) n+O(n)(b) 2n+O(n)(c) n/2(d) nMy question is from Binary Trees topic in division Binary Trees of Data Structures & Algorithms IThe question was asked in unit test.

General ordered tree can be encoded into binary trees.(a) true(b) falseAsked question is from Binary Trees in portion Binary Trees of Data Structures & Algorithms II have been asked this question by my school teacher while I was bunking the class.

How many types of insertion are performed in a binary tree?(a) 1(b) 2(c) 3(d) 4Query is from Binary Trees topic in division Binary Trees of Data Structures & Algorithms IThe question was posed to me in an internship interview.

How many common operations are performed in a binary tree?(a) 1(b) 2(c) 3(d) 4This intriguing question comes from Binary Trees topic in division Binary Trees of Data Structures & Algorithms IThe question was posed to me during an online exam.

A binary tree is a rooted tree but not an ordered tree.(a) true(b) falseI need to ask this question from Binary Trees topic in division Binary Trees of Data Structures & Algorithms IThis question was addressed to me during an interview.

The following given tree is an example for?(a) Binary tree(b) Binary search tree(c) Fibonacci tree(d) AVL treeMy question is from Binary Trees topic in section Binary Trees of Data Structures & Algorithms IThe question was posed to me in a national level competition.

What is the maximum number of children that a binary tree node can have?(a) 0(b) 1(c) 2(d) 3This intriguing question comes from Binary Trees topic in section Binary Trees of Data Structures & Algorithms IThe question was posed to me in exam.

Which of the following traversing algorithm is not used to traverse in a tree?(a) Post order(b) Pre order(c) Post order(d) RandomizedQuestion is taken from Binary Trees using Linked Lists in division Binary Trees of Data Structures & Algorithms IThe question was posed to me in an interview for job.

How many children does a binary tree have?(a) 2(b) any number of children(c) 0 or 1 or 2(d) 0 or 1The above asked question is from Binary Trees using Array topic in division Binary Trees of Data Structures & Algorithms II had been asked this question during an interview for a job.