1 Crore+ students have signed up on EduRev. Have you? 
A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.
I. 81, 537, 102, 439, 285, 376, 305
II. 52, 97, 121, 195, 242, 381, 472
III. 142, 248, 520, 386, 345, 270, 307
IV. 550, 149, 507, 395, 463, 402, 270
Q. Suppose the BST has been unsuccessfully searched for key 273. Which all of the above sequences list nodes in the order in which we could have encountered them in the search?
Key to be searched 273:
A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.
I. 81, 537, 102, 439, 285, 376, 305
II. 52, 97, 121, 195, 242, 381, 472
III. 142, 248, 520, 386, 345, 270, 307
IV. 550, 149, 507, 395, 463, 402, 270
Q. Which of the following statements is TRUE?
A: I and IV are not in ascending order
B: If 439 is root, It should be 1st element in preorder
D: IV is a postorder sequence of some BST with 149 as the root, => False
How many distinct BSTs can be constructed with 3 distinct keys?
^{2n}C_{n}/(n+1) = ^{6}C_{3}/4 = 5
What is the worst case possible height of RedBlack tree? Assume base of Log as 2 in all options
Is the following statement valid? A RedBlack Tree which is also a perfect Binary Tree can have all black nodes
A perfect BST with all black nodes doesn't violate any of the RedBlack tree properties.
Which of the following operations are used by RedBlack trees to maintain balance during insertion/deletion?
a) Recoloring of nodes
b) Rotation (Left and Right)
Both recoloring and rotation operations are used during insertion and deletion.
A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function g(x) for each node x. If the cost of computing g(x) is min{no. of leafnodes in leftsubtree of x, no. of leafnodes in rightsubtree of x} then the worstcase time complexity of the program is
The recurrence relation for the recursive function is T(N) = 2 * T(N/2) + n/2
Where N is the total no. of nodes in the tree.
T(N) = 2 * (2*T(N/2) + n/2) + n/2
= 4 * T(N/2) + 3(n/2)
Solve this till T(1) i.e. till we reach the root.
T(N) = c * T(N / 2^i) + (2*i  1) * (n/2)
Where i = lg(N)
= lg((2n  1) / 2)
O(c * T(N / 2^i) + (2*i  1) * (n/2)) reduces to
O((2*i  1) * (n/2))
O((2*( lg((2n  1) / 2))  1) * (n/2)) ...sub the value of i.
O(n * ln(n))
AVL tree is a balanced tree.
AVL tree's time complexity of searching = θ(logn)
But a binary search tree, may be skewed tree, so in worst case BST searching time = θ(n)
Given two Balanced binary search trees, B1 having n elements and B2 having m elements, what is the time complexity of the best known algorithm to merge these trees to form another balanced binary tree containing m+n elements ?
O(m+n) as we can first perform inorder on both the trees and store them in two separate arrays. Now we have two sorted sequences and we can merge them in O(m+n) using standard merge algorithm and on the final sorted array we can use the binary search to create the tree using Recursion. Recursively adding middle element at the root and repeating the same process for left and right subarrays.
The worst case running time to search for an element in a balanced in a binary search tree with n2^n elements is
Time taken to search an element is where h is the height of Binary Search Tree (BST). The growth of height of a balanced BST is logerthimic in terms of number of nodes. So the worst case time to search an element would be which is Which is] which can be written as.
What is the maximum height of any AVLtree with 7 nodes? Assume that the height of a tree with a single node is 0.
AVL trees are binary trees with the following restrictions. 1) the height difference of the children is at most 1. 2) both children are AVL trees Following is the most unbalanced AVL tree that we can get with 7 nodes
A Binary Search Tree is AVL if balance factor of every node is either 1 or 0 or 1. Balance factor of a node X is [(height of X>left)  (height of X>right)]. In Tree B, the node with value 50 has balance factor 2. That is why B is not an AVL tree.
Consider the following AVL tree.
Q. Which of the following is updated AVL tree after insertion of 70
Refer following for steps used in AVL insertion. AVL Tree  Set 1 (Insertion)
After insertion of 70, tree becomes following
We start from 50 and travel up. We keep travelling up till we find an unbalanced node. In above case, we reach the node 60 and see 60 got unbalanced after insertion and this is Right Left Case. So we need to apply two rotations
Which of the following is a selfadjusting or selfbalancing Binary Search Tree
See Splay Tree, AVL Tree and Red Black Tree
Consider the following leftrotate and rightrotate functions commonly used in selfadjusting BSTs
Q.
Which of the following is tightest upper bound for leftrotate and rightrotate operations.
The rotation operations (left and right rotate) take constant time as only few pointers are being changed there. Following are C implementations of leftrotate and rightrotate 1
Red Black Tree with n nodes has height <= 2Log2(n+1) AVL Tree with n nodes has height less than Log_{φ}(√5(n+2))  2. Therefore, the AVL trees are more balanced compared to Red Black Trees, but they may cause more rotations during insertion and deletion. So if your application involves many frequent insertions and deletions, then Red Black trees should be preferred. And if the insertions and deletions are less frequent and search is more frequent operation, then AVL tree should be preferred over Red Black Tree.
Which of the following is true about Red Black Trees?
Which of the following is true about AVL and Red Black Trees?
Refer Red Black Tree Insertion and AVL Tree Insertion
The number of edges from the root to the node is called __________ of the tree.
150 docs215 tests

Use Code STAYHOME200 and get INR 200 additional OFF

Use Coupon Code 
150 docs215 tests








