Explore topic-wise InterviewSolutions in .

The correct option is (a) self adjusting BINARY SEARCH TREES

The best EXPLANATION: Splay trees are HEIGHT balanced, self adjusting BST’s.

The correct option is (C) O (log n)

The best I can EXPLAIN: A LOT of applications have been implemented using Top TREE interface. Maintaining a dynamic set of weighted trees is one such application which can be implemented with O (log n) time complexity.

The correct answer is (a) Merge

The best EXPLANATION: Link returns a single tree having DIFFERENT vertices from top trees. Cut removes the EDGE from the top tree. Expose is USED to implement queries on top trees. While merge is an internal operation used to merge two clusters and return as a parent cluster.

The CORRECT option is (d) All of the mentioned

The explanation is: Link returns a single tree having DIFFERENT VERTICES from top trees. Cut removes the edge from the top tree. Expose is used to IMPLEMENT queries on top trees. HENCE all of the options are used as dynamic operations.

Correct answer is (d) All of the mentioned

The best I can explain: TOP tree can be considered as a binary tree if the nodes form a CLUSTER, LEAVES ACT as an EDGE and the root of the top tree acts as a tree itself. Then the top tree is called binary tree.

The CORRECT OPTION is (a) 0

The best EXPLANATION: Tree having a single vertex has no clusters of tree present in the structure. Therefore, there are empty top trees in a tree having a single vertex. Trees with one NODE are single node.

Right answer is (a) O (n)

BEST explanation: GENERALLY, trees have weight on its edges. ALSO there is one to one correspondence of the edges with the TOP trees. Therefore, top trees can be INITIALIZED in O (n) time.

Correct answer is (a) True

For explanation: Top tree data STRUCTURE is used to maintain a dynamic FOREST USING link or cut operations. Top tree is a type of data structure which is based on unrooted dynamic BINARY tree and is used to solve path related problems.

Right OPTION is (a) True

Explanation: If A ꓵ B is a SINGLETON set where A and B are two clusters, that is there are only ONE NODE that is common between the clusters then they are known as Merge able cluster.

Right option is (a) TOP Tree

Easy explanation - Top tree data STRUCTURE is used to maintain a DYNAMIC forest USING link or cut operations. Top tree is a type of data structure which is based on unrooted dynamic binary tree and is used to SOLVE path related problems.

Correct answer is (B) 1

For explanation: A cluster containing only single edge is known as Edge cluster. So there are in total 1 edge present in edge cluster. Cluster in data STRUCTURE is defined as the subtree that is CONNECT having maximum of 2 vertices known as BOUNDARY Vertices.

Correct option is (a) 0

To explain: If a cluster has no EDGES and contains only one vertex KNOWN as boundary vertex then, it is known as leaf cluster. So a leaf cluster doesn’t contain any edges. It is also known as POINT cluster.

Right choice is (a) 2

The best I can EXPLAIN: There are at least 2 edges present in path cluster. Cluster in data structure is defined as the SUBTREE that is connect having maximum of 2 VERTICES known as BOUNDARY Vertices.

Right answer is (d) 2

The BEST I can explain: Top tree is defined for a SET having a maximum of 2 VERTICES for its underlying tree. Those sets having at maximum 2 vertices is CALLED External Boundary Vertices.

Right ANSWER is (a) Divide and Conquer

The best explanation: TOP TREE is a TYPE of data structure which is based on unrooted dynamic binary tree and is used to solve PATH related problems. It allows an algorithm called divide and conquer.

The correct OPTION is (a) many inserts, many SEARCHES and when managing more ITEMS respectively

Easiest EXPLANATION - Red black when frequent inserts and deletes, AVL when less frequent inserts and deletes, B-tree when using paging from a slow storage DEVICE.

Correct option is (b) because of resizing issues of hash table and BETTER ordering in redblack trees

For explanation: Redblack trees have O(logn) for ordering ELEMENTS in terms of finding first and next elements. also whenever table size increases or DECREASES in hash table you need to perform rehashing which can be very expensive in real time. also red black stores elements in SORTED ORDER rather than input order.

Correct OPTION is (a) when there are more insertions or deletions

For explanation: Though both trees are balanced, when there are more insertions and deletions to make the TREE balanced, AVL trees should have more rotations, it would be BETTER to use red-black. but if more search is required AVL trees should be USED.

The correct option is (c) can be USED in process schedulers, maps, sets

Easiest explanation - RB tree is used for Linux kernel in the form of completely fair SCHEDULER process SCHEDULING algorithm. It is used for faster insertions, RETRIEVALS.

Right option is (a) a COLOR which is either red or black and root should always be black color only

The BEST EXPLANATION: An EXTRA attribute which is a color red or black is used. root is black because if it is red then one of red-black TREE property which states that number of black nodes from root to null nodes must be same, will be violated.

The CORRECT answer is (a) all basic operations and set intersection, set union and subset test

Explanation: The speciality of a weight BALANCED tree is a part from basic operations we can perform COLLECTIVE operations LIKE set intersection, which helps in rapid prototyping in functional programming LANGUAGES.

Right option is (a) weight[n.left] >= a*weight[n] and weight[n.right] >= a*weight[n].

For explanation: The TREE is SAID to be a-balanced if the condition is satisfied. and ‘a’ VALUE will be DETERMINED during tree FORMATION. large value of ‘a’ is more effective.

Right answer is (a) dynamic SETS, dictionaries, SEQUENCES, maps

Explanation: They are a type of self balancing TREES which are mostly USED in storing key-value pairs, which is mostly used in functional programming languages. they are very USEFUL to maintain big set of ordered objects.

Correct ANSWER is (a) A binary TREE that stores the SIZES of subtrees in nodes

The EXPLANATION is: Unlike AVL and redblack TREES which uses height and color as book keeping information, weight balanced trees use the size of subtrees.

The correct answer is (a) true

The explanation is: Range minmum query is finding the MINIMUM element in a given subarray of an ARRAY. Constant time is achieved by storing the Cartesian trees for all the blocks in the array. Rmq’s are used in STRING MATCHINGS, computing lowest COMMON ancestor and longest common prefix of a sring.

Right choice is (a) additional value, which is a priority value to the key generated randomly

For explanation: A cartesian tree, if feeded with a sorted sequence will generate a straight path (or in tree terminology a skew tree). moreover a cartesian tree basing on same values from the search keys DOESNOT work well. so a cartesian tree with priority value in ADDITION to search key is called TREAP.

Correct option is (c) minimum range QUERY and lowest common ancestors

Easiest explanation - In a cartesian TREE minimum value can be found by finding lowest common ancestor for the extreme ELEMENTS. consider 11,9,19,16 the lowest element is 9 and is a lowest common ancestor for 11 and 16. and by applying few techniques cartesian tree can be used to even find lowest common ancestors efficiently.

these can be done in CONSTANT time. tree can be constructed in linear time (this is the most EFFICIENT time for any tree construction) and takes space as many elements are there.

Right choice is (a) it sorts partially sorted set of DATA quickly

The explanation is: It can sort a set which requires only some sorting or DISPLACEMENTS. for EXAMPLE consider 78, 79, 80, 82, 81, 83, In this only 81 and 82 MUST be swaped to make it a complete sorted set, in this case CARTESIAN sort comes to the rescue.

The correct choice is (a) true

The BEST I can explain: A tree with heap property (parent is EITHER small or big than CHILDREN) and when traversed in inorder yields the given input SEQUENCE is called as a cartesian tree. as the above figure satisies both the properties. note that even MIN heap tree can be generated. the above is a max heap tree.

The correct OPTION is (c) a tree which obeys heap property and WHOSE inorder traversal yields the GIVEN sequence

The explanation is: A tree with heap property (parent is either small or BIG than children) and when traversed in inorder yields the given input sequence. refer below DIAGRAM question for clarity.

The correct choice is (b) AVL tree store balance factor in every node which costs space

The explanation is: Every node in an AVL tree need to store the balance factor (-1, 0, 1) HENCE space costs to O(n), n being number of nodes. but in red-black we can use the SIGN of number (if numbers being stored are only POSITIVE) and hence save space for storing balancing information. there are even other REASONS where redblack is mostly prefered.

Correct choice is (a) LOG(n) where n is the number of nodes

To EXPLAIN: At every level we can form a TREE with difference in HEIGHT between subtrees to be ATMOST 1 and so there can be log(n) such levels since height of AVL tree is log(n).

Right option is (b) find the median of the SET of elements GIVEN, MAKE it as root and construct the tree

Easy explanation - Sort the given INPUT, find the median element among them, make it as root and construct left and right subtrees with elements LESSER and greater than the median element recursively. this ensures the subtrees differ only by height 1.

The correct option is (a) true

Easy explanation - It is INTERESTING to NOTE that after INSERTION, only the path from that POINT to node or only that subtrees are imbalanced interms of HEIGHT.

Right option is (B) log(P)

Easy explanation - Consider height of TREE to be ‘he’, then number of nodes which TOTALS to p can be WRITTEN in terms of height as N(he)=N(he-1)+1+N(he-2). since N(he) which is p can be written in terms of height as the beside recurrence relation which on solving gives N(he)= O(logp) as worst case height.

Right answer is (a) to avoid formation of skew trees

Easy EXPLANATION - In real world dealing with random values is often not POSSIBLE, the probability that u are dealing with NON random values(like SEQUENTIAL) leads to mostly skew trees, which leads to worst case. hence we make height balance by ROTATIONS.

Right choice is (a) a TREE which is BALANCED and is a HEIGHT balanced tree

Explanation: It is a self balancing tree with height difference ATMOST 1.

The CORRECT answer is (a) AA-tree

Easiest EXPLANATION - Since an AA-tree TENDS to be FLATTER, AA-tree has a faster SEARCH time than a Red-Black tree.

The correct option is (B) RIGHT rotation

Easiest explanation - B is INITIALLY the right child of X. It is then ROTATED right side and now, B is the left child of P.

The correct choice is (C) It should be strictly less than that of its PARENT

For EXPLANATION: The level of a left node should be strictly less than that of its parent. The level of a right node is less than or EQUAL to that of its parent.

Right OPTION is (a) ARNE ANDERSON

To explain: AA-tree is INVENTED by Arne Anderson. Daniel Sleator invented Splay Tree. Rudolf Bayer invented a Red-Black tree. Jon Louis BENTLEY invented K-d tree.

The CORRECT choice is (a) True

The BEST explanation: AA- TREES make more rotations than a red-black tree since only two shapes are considered for an AA-Tree whereas SEVEN shapes are considered in Red-Black trees.

The correct answer is (d) Red-Black TREE

The BEST explanation: AA- Tree is a SMALL variation of Red-Black tree. AA-Trees overcome the complexity faced in performing insertion and deletion in Red-Black Trees.