BST

Question 1

EACH VERTEX CAN HAVE UP TO 2 CHILDREN

Answer 1

2 CHILDREN

Question 2

LEFT - SMALL , RIGHT-LARGER

Answer 2

DUPLICATES ARE STORED AS FREQUENCY - MULTISET

Question 3

AVL trees are self balancing binary tree with height O(log (n))

Question 4

Find Successor

Answer 4

1. if RIGHT exist, then min in the right subtree
2. no RIGTH exist, go to parent and traverse until the the first right turn from searching. Then parent of that right successor. Basically, it gives the first max of V (right turn)
3. if MAX in BST, then we go until root and not found. Result is -1

RIGHT (find min) or parent first right’s parent

Question 5

Find Predecessor

Answer 5

1. if left exist, then max in the subtree
2. if left not exist, parents’ first left, then parent
3. if no left find until ROOT then -1

Question 6

PRE, IN, POST

Answer 6

PPE- print as we visit FIRST time
IN - print as we visit SECOND time
POST - print as we visit THIRD time
https://www.youtube.com/watch?v=WLvU5EQVZqY

Question 7

BST element rank

Answer 7

Use IN ORDER to write in sorted order and find the index - starting with 1

Question 8

Ascending order

Answer 8

In order traversal

Question 9

Kth-smallest

Answer 9

Use ranking BST
https://www.youtube.com/watch?v=adAQs2FNuFo for later exam study

Question 10

Static/Dynamic

Answer 10

If no update, insert or delete then static. If there is then dynamic

Question 11

lower-bound

Answer 11

smallest value that is bigger than the value V to be found

Question 12

search/lower_bound/searchMin/SearchMax time complexity

Answer 12

O(h)
h- as tall as N for normal BST

Question 13

Skewed BST

Answer 13

only RIGHT or only LEFT

Question 14

time complexity: O(N Log(N)) to insertions of N elements and then O(N) for in-order to get sorted

Answer 14

But rarely used

Question 15

Height is ZERO based

Answer 15

root - 0

Question 16

in normal BST, O(h) for finding find for others

Answer 16

insertion O(1) as at the leaf
deletion of no child - O(1)
deletion with one child - O(1)
deletion with two child - O(h) for finding successor

Question 17

skewed BST is nothing but

Answer 17

linked list

Question 18

Height

Answer 18

Number of edges under the rode to leaf
-max route

Question 19

AVL lower bound height

Answer 19

log2(N)

Question 20

AVL two soviet inventors

Answer 20

Georgy Adelson-Velskii
Evgenii Landis
1962

Question 21

AVL height

Answer 21

< 2 * log(N)

Question 22

AVL BF - balance factor

Answer 22

number of left edges - number of right edges. And should be in {-1,0,1}
https://www.youtube.com/watch?v=u3OVSkuOdqI

Question 23

rotations

Answer 23

More on left -> rotate right
More on right -> rotate left

LL -> Left rotation
RR -> Right rotation
LR -> from root left followed by right
so, first child left rotation
then right rotation
RL -> from root right followed by left