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

101.	What is the prime condition of AA-tree which makes it simpler than a red-black tree?(a) Only right children can be red(b) Only left children can be red(c) Right children should strictly be black(d) There should be no left childrenMy question is from Binary Trees topic in section Binary Trees of Data Structures & Algorithms II have been asked this question in an interview for job.
Answer» Correct ANSWER is (a) Only right children can be RED Explanation: The prime CONDITION of AA-Tree is that only the right children can be red to eliminate possible restructuring cases.

Discussion

102.	How many different shapes does maintenance of AA-Tree need to consider?(a) 7(b) 5(c) 2(d) 3Origin of the question is Binary Trees topic in chapter Binary Trees of Data Structures & Algorithms II had been asked this question by my college professor while I was bunking the class.
Answer» Right CHOICE is (c) 2 To explain: An AA-TREE needs to CONSIDER only TWO shapes UNLIKE a red-black tree which needs to consider seven shapes of transformation.

Discussion

103.	In an AA-tree, we process split first, followed by a skew.(a) True(b) FalseMy question is based upon Binary Trees in division Binary Trees of Data Structures & Algorithms IThis question was addressed to me in an internship interview.
Answer» CORRECT answer is (b) False For EXPLANATION: In an AA-tree, skew is processed first FOLLOWED by a SPLIT.

Discussion

104.	What are the two different operations done in an AA-Tree?(a) shift and color(b) skew and split(c) zig and zag(d) enqueue and dequeueMy doubt stems from Binary Trees in section Binary Trees of Data Structures & Algorithms IThis question was addressed to me in an internship interview.
Answer» The CORRECT option is (b) SKEW and split The best explanation: A skew REMOVES a LEFT HORIZONTAL link by right rotation and a split removes a right horizontal link by left rotation.

Discussion

105.	How will you remove a left horizontal link in an AA-tree?(a) by performing right rotation(b) by performing left rotation(c) by deleting both the elements(d) by inserting a new elementMy doubt stems from Binary Trees in division Binary Trees of Data Structures & Algorithms II have been asked this question in final exam.
Answer» RIGHT option is (a) by performing right rotation The explanation is: A left HORIZONTAL LINK is REMOVED by right rotation.A right horizontal link is removed by left rotation.

Discussion

106.	Which of the following is the correct definition for a horizontal link?(a) connection between node and a child of equal levels(b) connection between two nodes(c) connection between two child nodes(d) connection between root node and leaf nodeQuestion is from Binary Trees in section Binary Trees of Data Structures & Algorithms II got this question in an online interview.
Answer» The correct choice is (a) CONNECTION between node and a child of EQUAL LEVELS The BEST I can explain: A horizontal link is a connection between a node and a child of equal levels.

Discussion

107.	AA Trees are implemented using?(a) Colors(b) Levels(c) Node size(d) HeapsMy question comes from Binary Trees topic in division Binary Trees of Data Structures & Algorithms II have been asked this question during an interview.
Answer» The correct answer is (b) LEVELS The best I can explain: AA TREES are implemented USING levels instead of COLORS to overcome the disadvantages of Red-Black trees.

Discussion

108.	Is mathematical randomized tree can be generated using beta distribution.(a) True(b) FalseMy question is from Binary Trees topic in portion Binary Trees of Data Structures & Algorithms IThis question was addressed to me in a national level competition.
Answer» Right OPTION is (a) True Explanation: Beta distribution can be USED using a different shape to GENERATE a randomized BINARY search tree to create a special type of tree known as a botanical tree.

Discussion

109.	What is the probability of selecting a tree uniformly at random?(a) Equal to Catalan Number(b) Less Than Catalan Number(c) Greater than Catalan Number(d) Reciprocal of Catalan NumberMy question is based upon Binary Trees topic in division Binary Trees of Data Structures & Algorithms II have been asked this question during an interview for a job.
Answer» The correct choice is (d) Reciprocal of Catalan Number The best I can explain: Catalan number is a sequence of NATURAL number that is used in counting problem. Hence it is found that the selecting off a TREE UNIFORMLY at RANDOM is reciprocal of Catalan number.

Discussion

110.	Is Treap a randomized tree.(a) True(b) FalseMy question is from Binary Trees in portion Binary Trees of Data Structures & Algorithms IThe question was asked during an interview for a job.
Answer» The CORRECT answer is (a) True The explanation is: TREAP is a type of data structure which is a combination of binary tree and heap. It is an example of a randomized binary SEARCH tree. It stores value in PAIRS.

Discussion

111.	What is the expected number of leaves in a randomized binary search tree?(a) n + 1(b) (n + 1)/3(c) (n + 1)/2(d) n + 3This question is from Binary Trees in portion Binary Trees of Data Structures & Algorithms IThis question was addressed to me by my college professor while I was bunking the class.
Answer» The correct answer is (B) (n + 1)/3 To explain: In a RANDOM mathematical model, the expected value of NUMBER of leaves in a randomized binary search tree is found to be exactly (n + 1)/3 USING probability.

Discussion

112.	What is the range of β in finding the length of the longest path in a randomized binary search tree?(a) (-1, 0)(b) (1, 0)(c) (0, 5)(d) (0, 1)I'd like to ask this question from Binary Trees in chapter Binary Trees of Data Structures & Algorithms IThe question was asked in semester exam.
Answer» Right option is (d) (0, 1) The explanation is: The LONGEST path in a RANDOMIZED binary SEARCH tree, but it has been found that the longest LENGTH is around 4.311 log x for node x. This is also equal to 1/β log x where β lies in the RANGE (0, 1).

Discussion

113.	What is the longest length path for a node x in random binary search tree for the insertion process?(a) log x(b) x^2(c) x!(d) 4.311 log xMy enquiry is from Binary Trees in division Binary Trees of Data Structures & Algorithms II got this question during an interview.
Answer» Right option is (d) 4.311 log X Best explanation: Although it is difficult to find the length of the longest PATH in randomized binary search tree, but it has been found that the longest length is around 4.311 log x.

Discussion

114.	What is the expected depth of a node in a randomized binary search tree?(a) log n(b) n!(c) n^2(d) 2 log n + O(1)Asked question is from Binary Trees topic in section Binary Trees of Data Structures & Algorithms IThis question was posed to me in quiz.
Answer» The correct CHOICE is (d) 2 log n + O(1) For explanation: The expected value of depth of a node that is for a node a, the expected value of length of path from ROOT to node a is FOUND to be at most 2 log n + O(1).

Discussion

115.	How many randomized binary search trees can be formed by the numbers (1, 3, 2)?(a) 2(b) 3(c) 6(d) 5The above asked question is from Binary Trees topic in section Binary Trees of Data Structures & Algorithms II have been asked this question in an interview for internship.
Answer» The correct answer is (d) 5 Easy EXPLANATION - As there are 3 numbers (1, 3, 2) so total of 6 COMBINATIONS can be formed using three numbers but Since (2, 1, 3) and (2, 3, 1) are same so in total there are 5 randomized binary search tree that can be formed.

Discussion

116.	Which process forms the randomized binary search tree?(a) Stochastic Process(b) Branching Process(c) Diffusion Process(d) Aggregation ProcessThe origin of the question is Binary Trees topic in division Binary Trees of Data Structures & Algorithms II had been asked this question in an international level competition.
Answer» The correct choice is (a) STOCHASTIC Process To explain: The randomized binary search tree is formed by the stochastic process. The stochastic process or also CALLED RANDOM process is a MATHEMATICAL tool or OBJECT including random variables.

Discussion

117.	Which of the following is not a random tree?(a) Treap(b) Random Binary Tree(c) Uniform Spanning Tree(d) AVL TreeMy question is based upon Binary Trees in chapter Binary Trees of Data Structures & Algorithms IThe question was asked during an interview.
Answer» CORRECT choice is (d) AVL Tree Explanation: Treap, also known as random binary search tree, Random binary tree and UNIFORM SPANNING tree are all random tree. Random tree is a tree formed by a random process of addition and deletion of nodes. AVL tree is a self – balanced binary search tree.

Discussion

118.	Binary tree sort implemented using a self balancing binary search tree takes O(n log n) time in the worst case but still it is slower than merge sort.(a) True(b) FalseMy question is taken from Binary Trees topic in portion Binary Trees of Data Structures & Algorithms II got this question by my school principal while I was bunking the class.
Answer» Correct choice is (a) True The best explanation: The worst case PERFORMANCE of binary tree SORT is O(N log n) when it is implemented using a self balancing binary SEARCH tree. Self balancing binary search trees perform transformations to balance the tree, which caused balancing overhead. DUE to this overhead, binary tree sort is slower than merger sort.

Discussion

119.	The minimum height of self balancing binary search tree with n nodes is _____(a) log2(n)(b) n(c) 2n + 1(d) 2n – 1My question is from Binary Trees topic in portion Binary Trees of Data Structures & Algorithms IThis question was posed to me in homework.
Answer» Right option is (a) log2(n) Explanation: Self – balancing BINARY trees adjust the height by performing TRANSFORMATIONS on the tree at key insertion TIMES, in order to keep the height PROPORTIONAL to log2(n).

Discussion

120.	In which of the following self – balancing binary search tree the recently accessed element can be accessed quickly?(a) AVL tree(b) AA tree(c) Splay tree(d) Red – Black treeThis intriguing question originated from Binary Trees in section Binary Trees of Data Structures & Algorithms IThe question was asked during an online exam.
Answer» Right ANSWER is (C) Splay tree For EXPLANATION: In a Splay tree, the RECENTLY accessed element can be accessed quickly. In Splay tree, the frequently accessed nodes are moved towards the root so they are QUICK to access again.

Discussion

121.	A self – balancing binary search tree can be used to implement ________(a) Priority queue(b) Hash table(c) Heap sort(d) Priority queue and Heap sortThe above asked question is from Binary Trees in section Binary Trees of Data Structures & Algorithms II have been asked this question in an interview for job.
Answer» Right choice is (a) Priority queue Explanation: SELF-balancing binary search trees can be used to construct and MAINTAIN ordered LISTS, to achieve the OPTIMAL worst case performance. So, self – balancing binary search tree can be used to implement a priority queue, which is ordered list.

Discussion

122.	Which of the following is a self – balancing binary search tree?(a) 2-3 tree(b) Threaded binary tree(c) AA tree(d) TreapQuestion is from Binary Trees in portion Binary Trees of Data Structures & Algorithms IThe question was posed to me during an online exam.
Answer» Right option is (c) AA tree Easiest explanation - An AA tree, which is a VARIATION of red-black tree, is a self – balancing BINARY search tree. 2-3 is B-tree of order 3 and TREAT is a randomized binary search tree. A THREADED binary tree is not a balanced tree.

Discussion

123.	Self – balancing binary search trees have a much better average-case time complexity than hash tables.(a) True(b) FalseMy question is taken from Binary Trees in chapter Binary Trees of Data Structures & Algorithms IThis question was posed to me in class test.
Answer» Correct CHOICE is (b) False Easy explanation - For lookup, insertion and DELETION hash table TAKE O(1) TIME in average-case while self – balancing binary search trees takes O(log n). Therefore, hash tables perform better in average-case.

Discussion

124.	Associative arrays can be implemented using __________(a) B-tree(b) A doubly linked list(c) A single linked list(d) A self balancing binary search treeThe query is from Binary Trees topic in section Binary Trees of Data Structures & Algorithms II had been asked this question in final exam.
Answer» The correct choice is (d) A self BALANCING binary search tree Easiest EXPLANATION - ASSOCIATIVE arrays can be implemented using a self balancing binary search tree as the worst-case time performance of self – balancing binary search trees is O(log n).

Discussion

125.	An AVL tree is a self – balancing binary search tree, in which the heights of the two child sub trees of any node differ by _________(a) At least one(b) At most one(c) Two(d) At most twoMy question comes from Binary Trees in chapter Binary Trees of Data Structures & Algorithms IThe question was posed to me in a national level competition.
Answer» Correct CHOICE is (b) At most one Easiest EXPLANATION - In an AVL tree, the difference between HEIGHTS of the two child sub trees of any node is at most one. If the height DIFFERS by more than one, AVL tree PERFORMS rotations to balance the tree.

Discussion

126.	The binary tree sort implemented using a self – balancing binary search tree takes ______ time is worst case.(a) O(n log n)(b) O(n)(c) O(n^2)(d) O(log n)I'd like to ask this question from Binary Trees topic in chapter Binary Trees of Data Structures & Algorithms IThe question was posed to me at a job interview.
Answer» CORRECT choice is (a) O(N log n) BEST explanation: The worst case running time of the BINARY tree sort is O(n^2). But, the worst case running time can be improved to the O(n log n) using a SELF – balancing binary search tree.

Discussion

127.	Which of the following is not the self balancing binary search tree?(a) AVL Tree(b) 2-3-4 Tree(c) Red – Black Tree(d) Splay TreeThis interesting question is from Binary Trees in chapter Binary Trees of Data Structures & Algorithms IThis question was addressed to me in unit test.
Answer» Correct choice is (b) 2-3-4 Tree The BEST I can explain: 2-3-4 Tree is BALANCED search trees. But it is not a binary tree. So, it is not a SELF balancing binary tree. AVL tree, Red-Black Tree and SPLAY tree are self balancing binary search tree.

Discussion

128.	The figure shown below is a balanced binary tree. If node P is deleted, which of the following nodes will get unbalanced?(a) U(b) M(c) H(d) AMy doubt is from Binary Trees in section Binary Trees of Data Structures & Algorithms II have been asked this question in a job interview.
Answer» The correct choice is (a) U The best explanation: Node U will get unbalanced if node P is DELETED, because it’s balance factor will BECOME -2.

Discussion

129.	AVL trees are more balanced than Red-black trees.(a) True(b) FalseThe origin of the question is Binary Trees in portion Binary Trees of Data Structures & Algorithms II got this question in an interview for job.
Answer» Right choice is (a) True The BEST I can explain: AVL TREE is more balanced than a Red-black tree because AVL tree has less height than Red-black tree given that both TREES have the same number of elements.

Discussion

130.	Which of the following is an advantage of balanced binary search tree, like AVL tree, compared to binary heap?(a) insertion takes less time(b) deletion takes less time(c) searching takes less time(d) construction of the tree takes less time than binary heapQuestion is from Binary Trees topic in portion Binary Trees of Data Structures & Algorithms IThe question was asked by my school teacher while I was bunking the class.
Answer» The correct choice is (a) INSERTION takes less TIME Best EXPLANATION: Insertion and deletion, in both the binary heap and balanced binary search tree takes O(LOG n). But SEARCHING in balanced binary search tree requires O(log n) while binary heap takes O(n). Construction of balanced binary search tree takes O(nlog n) time while binary heap takes O(n).

Discussion

131.	Two balanced binary trees are given with m and n elements respectively. They can be merged into a balanced binary search tree in ____ time.(a) O(m+n)(b) O(mn)(c) O(m)(d) O(mlog n)My question is taken from Binary Trees topic in chapter Binary Trees of Data Structures & Algorithms IThe question was posed to me in a job interview.
Answer» CORRECT option is (a) O(m+n) To explain: FIRST we STORE the in-order traversals of both the trees in two separate arrays and then we can merge these sorted sequences in O(m+n) TIME. And then we construct the balanced tree from this final sorted array.

Discussion

132.	Which of the following data structures can be efficiently implemented using height balanced binary search tree?(a) sets(b) priority queue(c) heap(d) both sets and priority queueThe above asked question is from Binary Trees topic in chapter Binary Trees of Data Structures & Algorithms IThe question was asked by my school principal while I was bunking the class.
Answer» Correct CHOICE is (d) both sets and priority queue For explanation: Height-Balanced binary search tree can PROVIDE an EFFICIENT implementation of sets, priority queues.

Discussion

133.	Balanced binary tree with n items allows the lookup of an item in ____ worst-case time.(a) O(log n)(b) O(nlog 2)(c) O(n)(d) O(1)My enquiry is from Binary Trees in division Binary Trees of Data Structures & Algorithms II had been asked this question in quiz.
Answer» The CORRECT ANSWER is (a) O(LOG N) Easiest explanation - Searching an item in balanced binary is fast and worst-case TIME complexity of the search is O(log n).

Discussion

134.	Which of the following tree data structures is not a balanced binary tree?(a) AVL tree(b) Red-black tree(c) Splay tree(d) B-treeI would like to ask this question from Binary Trees in portion Binary Trees of Data Structures & Algorithms IThis question was addressed to me during an interview.
Answer» RIGHT choice is (d) B-TREE For explanation: All the tree data structures given in options are BALANCED, but B-tree can have more than TWO children.

Discussion

135.	A binary tree is balanced if the difference between left and right subtree of every node is not more than ____(a) 1(b) 3(c) 2(d) 0The question is from Binary Trees in portion Binary Trees of Data Structures & Algorithms II got this question during an online exam.
Answer» Right option is (a) 1 Best EXPLANATION: In a BALANCED binary tree the heights of two SUBTREES of every node never DIFFER by more than 1.

Discussion

136.	Figure below is a balanced binary tree. If a node inserted as child of the node R, how many nodes will become unbalanced?(a) 2(b) 1(c) 3(d) 0The origin of the question is Binary Trees topic in chapter Binary Trees of Data Structures & Algorithms IThis question was addressed to me by my college director while I was bunking the class.
Answer» Right OPTION is (b) 1 To explain: Only the node P will become unbalanced, with BALANCE FACTOR +2.

Discussion

137.	The balance factor of a node in a binary tree is defined as _____(a) addition of heights of left and right subtrees(b) height of right subtree minus height of left subtree(c) height of left subtree minus height of right subtree(d) height of right subtree minus oneOrigin of the question is Binary Trees in section Binary Trees of Data Structures & Algorithms II got this question in homework.
Answer» The correct choice is (C) height of LEFT SUBTREE minus height of right subtree Explanation: For a node in a binary tree, the difference between the HEIGHTS of its left subtree and right subtree is known as BALANCE factor of the node.

Discussion

138.	What will be the height of a balanced full binary tree with 8 leaves?(a) 8(b) 5(c) 6(d) 4My question comes from Binary Trees topic in division Binary Trees of Data Structures & Algorithms II had been asked this question during an online exam.
Answer» The CORRECT choice is (d) 4 Easiest explanation - A balanced FULL binary tree with l LEAVES has height h, where h = log2l + 1. So, the height of a balanced full binary tree with 8 leaves =log28 + 1 = 3 + 1 = 4.

Discussion

139.	Which of the following is incorrect with respect to binary trees?(a) Let T be a binary tree. For every k ≥ 0, there are no more than 2k nodes in level k(b) Let T be a binary tree with λ levels. Then T has no more than 2^λ – 1 nodes(c) Let T be a binary tree with N nodes. Then the number of levels is at least ceil(log (N + 1))(d) Let T be a binary tree with N nodes. Then the number of levels is at least floor(log (N + 1))I want to ask this question from Binary Tree Properties in chapter Binary Trees of Data Structures & Algorithms IThe question was asked in semester exam.
Answer» The correct OPTION is (d) LET T be a binary tree with N NODES. Then the number of levels is at least floor(log (N + 1)) To explain: In a binary tree, there are atmost 2k nodes in level k and 2^k-1 total number of nodes. Number of levels is at least ceil(log(N+1)).

Discussion

140.	In a full binary tree if there are L leaves, then total number of nodes N are?(a) N = 2L(b) N = L + 1(c) N = L – 1(d) N = 2L – 1Question is taken from Binary Tree Properties topic in section Binary Trees of Data Structures & Algorithms II have been asked this question in an interview for job.
Answer» The correct ANSWER is (d) N = 2L – 1 The EXPLANATION is: The relation between number of nodes(N) and leaves(L) is N=2L-1.

Discussion

141.	In a full binary tree if number of internal nodes is I, then number of nodes N are?(a) N = 2I(b) N = I + 1(c) N = I – 1(d) N = 2I + 1This interesting question is from Binary Tree Properties in chapter Binary Trees of Data Structures & Algorithms IThe question was asked by my school teacher while I was bunking the class.
Answer» The correct answer is (d) N = 2I + 1 The explanation is: RELATION between NUMBER of INTERNAL nodes(I) and nodes(N) is N = 2I+1.

Discussion

142.	In a full binary tree if number of internal nodes is I, then number of leaves L are?(a) L = 2I(b) L = I + 1(c) L = I – 1(d) L = 2I – 1My query is from Binary Tree Properties in division Binary Trees of Data Structures & Algorithms IThe question was asked in examination.
Answer» RIGHT choice is (b) L = I + 1 The BEST explanation: Number of LEAF nodes in full binary tree is EQUAL to 1 + Number of INTERNAL Nodes i.e L = I + 1

Discussion

143.	Which of the following is not an advantage of trees?(a) Hierarchical structure(b) Faster search(c) Router algorithms(d) Undo/Redo operations in a notepadQuestion is taken from Binary Tree Properties in section Binary Trees of Data Structures & Algorithms II have been asked this question in my homework.
Answer» Right choice is (d) Undo/Redo operations in a notepad Best EXPLANATION: Undo/Redo operations in a notepad is an application of stack. Hierarchical STRUCTURE, FASTER search, Router algorithms are advantages of trees.

Discussion

144.	What is the average case time complexity for finding the height of the binary tree?(a) h = O(loglogn)(b) h = O(nlogn)(c) h = O(n)(d) h = O(log n)My question is based upon Binary Tree Properties topic in chapter Binary Trees of Data Structures & Algorithms II have been asked this question at a job interview.
Answer» RIGHT answer is (d) H = O(log n) The explanation is: The nodes are EITHER a part of left sub tree or the right sub tree, so we don’t have to traverse all the nodes, this MEANS the complexity is lesser than n, in the average case, assuming the nodes are SPREAD evenly, the time complexity becomes O(logn).

Discussion

145.	What is a complete binary tree?(a) Each node has exactly zero or two children(b) A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from right to left(c) A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right(d) A tree In which all nodes have degree 2The query is from Binary Tree Properties in division Binary Trees of Data Structures & Algorithms II had been asked this question by my school principal while I was bunking the class.
Answer» The CORRECT answer is (c) A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right Explanation: A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right is called complete binary tree. A Tree in which each NODE has exactly zero or two children is called FULL binary tree. A Tree in which the degree of each node is 2 except leaf NODES is called perfect binary tree.

Discussion

146.	What is a full binary tree?(a) Each node has exactly zero or two children(b) Each node has exactly two children(c) All the leaves are at the same level(d) Each node has exactly one or two childrenMy question is taken from Binary Tree Properties in portion Binary Trees of Data Structures & Algorithms IThe question was asked during an online exam.
Answer» The correct choice is (a) Each NODE has EXACTLY zero or two children Easy explanation - A full binary tree is a tree in which each node has exactly 0 or 2 children.

Discussion

147.	The number of edges from the node to the deepest leaf is called _________ of the tree.(a) Height(b) Depth(c) Length(d) WidthMy enquiry is from Binary Tree Properties in portion Binary Trees of Data Structures & Algorithms IThe question was asked in an interview for internship.
Answer» The correct option is (a) Height To EXPLAIN: The number of edges from the node to the DEEPEST LEAF is CALLED height of the tree.

Discussion

148.	The number of edges from the root to the node is called __________ of the tree.(a) Height(b) Depth(c) Length(d) WidthI would like to ask this question from Binary Tree Properties topic in division Binary Trees of Data Structures & Algorithms IThe question was asked by my school teacher while I was bunking the class.
Answer» The CORRECT option is (B) Depth The BEST I can explain: The number of edges from the root to the NODE is called depth of the tree.

Discussion

149.	In a binary search tree, which of the following traversals would print the numbers in the ascending order?(a) Level-order traversal(b) Pre-order traversal(c) Post-order traversal(d) In-order traversalI would like to ask this question from Inorder Traversal 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» RIGHT choice is (d) In-order traversal The best I can explain: In a binary search tree, a node’s left child is ALWAYS LESSER than the node and right child is greater than the node, HENCE an in-order traversal would print them in a non decreasing fashion.

Discussion

150.	Which of the following graph traversals closely imitates level order traversal of a binary tree?(a) Depth First Search(b) Breadth First Search(c) Depth & Breadth First Search(d) Binary SearchThis intriguing question comes from Inorder Traversal in portion Binary Trees of Data Structures & Algorithms II got this question by my college professor while I was bunking the class.
Answer» CORRECT option is (b) Breadth FIRST Search Best explanation: Both level order tree traversal and breadth first GRAPH traversal follow the principle that VISIT your NEIGHBORS first and then move on to further nodes.

Discussion

Explore topic-wise InterviewSolutions in .

How many different shapes does maintenance of AA-Tree need to consider?(a) 7(b) 5(c) 2(d) 3Origin of the question is Binary Trees topic in chapter Binary Trees of Data Structures & Algorithms II had been asked this question by my college professor while I was bunking the class.

In an AA-tree, we process split first, followed by a skew.(a) True(b) FalseMy question is based upon Binary Trees in division Binary Trees of Data Structures & Algorithms IThis question was addressed to me in an internship interview.

What are the two different operations done in an AA-Tree?(a) shift and color(b) skew and split(c) zig and zag(d) enqueue and dequeueMy doubt stems from Binary Trees in section Binary Trees of Data Structures & Algorithms IThis question was addressed to me in an internship interview.

AA Trees are implemented using?(a) Colors(b) Levels(c) Node size(d) HeapsMy question comes from Binary Trees topic in division Binary Trees of Data Structures & Algorithms II have been asked this question during an interview.

Is mathematical randomized tree can be generated using beta distribution.(a) True(b) FalseMy question is from Binary Trees topic in portion Binary Trees of Data Structures & Algorithms IThis question was addressed to me in a national level competition.

Is Treap a randomized tree.(a) True(b) FalseMy question is from Binary Trees in portion Binary Trees of Data Structures & Algorithms IThe question was asked during an interview for a job.

What is the expected number of leaves in a randomized binary search tree?(a) n + 1(b) (n + 1)/3(c) (n + 1)/2(d) n + 3This question is from Binary Trees in portion Binary Trees of Data Structures & Algorithms IThis question was addressed to me by my college professor while I was bunking the class.

What is the range of β in finding the length of the longest path in a randomized binary search tree?(a) (-1, 0)(b) (1, 0)(c) (0, 5)(d) (0, 1)I'd like to ask this question from Binary Trees in chapter Binary Trees of Data Structures & Algorithms IThe question was asked in semester exam.

What is the longest length path for a node x in random binary search tree for the insertion process?(a) log x(b) x^2(c) x!(d) 4.311 log xMy enquiry is from Binary Trees in division Binary Trees of Data Structures & Algorithms II got this question during an interview.

What is the expected depth of a node in a randomized binary search tree?(a) log n(b) n!(c) n^2(d) 2 log n + O(1)Asked question is from Binary Trees topic in section Binary Trees of Data Structures & Algorithms IThis question was posed to me in quiz.

How many randomized binary search trees can be formed by the numbers (1, 3, 2)?(a) 2(b) 3(c) 6(d) 5The above asked question is from Binary Trees topic in section Binary Trees of Data Structures & Algorithms II have been asked this question in an interview for internship.

Which of the following is not a random tree?(a) Treap(b) Random Binary Tree(c) Uniform Spanning Tree(d) AVL TreeMy question is based upon Binary Trees in chapter Binary Trees of Data Structures & Algorithms IThe question was asked during an interview.

The minimum height of self balancing binary search tree with n nodes is _____(a) log2(n)(b) n(c) 2n + 1(d) 2n – 1My question is from Binary Trees topic in portion Binary Trees of Data Structures & Algorithms IThis question was posed to me in homework.

Which of the following is a self – balancing binary search tree?(a) 2-3 tree(b) Threaded binary tree(c) AA tree(d) TreapQuestion is from Binary Trees in portion Binary Trees of Data Structures & Algorithms IThe question was posed to me during an online exam.

Self – balancing binary search trees have a much better average-case time complexity than hash tables.(a) True(b) FalseMy question is taken from Binary Trees in chapter Binary Trees of Data Structures & Algorithms IThis question was posed to me in class test.

Associative arrays can be implemented using __________(a) B-tree(b) A doubly linked list(c) A single linked list(d) A self balancing binary search treeThe query is from Binary Trees topic in section Binary Trees of Data Structures & Algorithms II had been asked this question in final exam.

Which of the following is not the self balancing binary search tree?(a) AVL Tree(b) 2-3-4 Tree(c) Red – Black Tree(d) Splay TreeThis interesting question is from Binary Trees in chapter Binary Trees of Data Structures & Algorithms IThis question was addressed to me in unit test.

The figure shown below is a balanced binary tree. If node P is deleted, which of the following nodes will get unbalanced?(a) U(b) M(c) H(d) AMy doubt is from Binary Trees in section Binary Trees of Data Structures & Algorithms II have been asked this question in a job interview.

AVL trees are more balanced than Red-black trees.(a) True(b) FalseThe origin of the question is Binary Trees in portion Binary Trees of Data Structures & Algorithms II got this question in an interview for job.

Balanced binary tree with n items allows the lookup of an item in ____ worst-case time.(a) O(log n)(b) O(nlog 2)(c) O(n)(d) O(1)My enquiry is from Binary Trees in division Binary Trees of Data Structures & Algorithms II had been asked this question in quiz.

Which of the following tree data structures is not a balanced binary tree?(a) AVL tree(b) Red-black tree(c) Splay tree(d) B-treeI would like to ask this question from Binary Trees in portion Binary Trees of Data Structures & Algorithms IThis question was addressed to me during an interview.

A binary tree is balanced if the difference between left and right subtree of every node is not more than ____(a) 1(b) 3(c) 2(d) 0The question is from Binary Trees in portion Binary Trees of Data Structures & Algorithms II got this question during an online exam.

What will be the height of a balanced full binary tree with 8 leaves?(a) 8(b) 5(c) 6(d) 4My question comes from Binary Trees topic in division Binary Trees of Data Structures & Algorithms II had been asked this question during an online exam.

In a full binary tree if there are L leaves, then total number of nodes N are?(a) N = 2*L(b) N = L + 1(c) N = L – 1(d) N = 2*L – 1Question is taken from Binary Tree Properties topic in section Binary Trees of Data Structures & Algorithms II have been asked this question in an interview for job.

In a full binary tree if number of internal nodes is I, then number of leaves L are?(a) L = 2*I(b) L = I + 1(c) L = I – 1(d) L = 2*I – 1My query is from Binary Tree Properties in division Binary Trees of Data Structures & Algorithms IThe question was asked in examination.

The number of edges from the node to the deepest leaf is called _________ of the tree.(a) Height(b) Depth(c) Length(d) WidthMy enquiry is from Binary Tree Properties in portion Binary Trees of Data Structures & Algorithms IThe question was asked in an interview for internship.

In a full binary tree if there are L leaves, then total number of nodes N are?(a) N = 2L(b) N = L + 1(c) N = L – 1(d) N = 2L – 1Question is taken from Binary Tree Properties topic in section Binary Trees of Data Structures & Algorithms II have been asked this question in an interview for job.

In a full binary tree if number of internal nodes is I, then number of leaves L are?(a) L = 2I(b) L = I + 1(c) L = I – 1(d) L = 2I – 1My query is from Binary Tree Properties in division Binary Trees of Data Structures & Algorithms IThe question was asked in examination.