Trees

Question 1

What is the depth of a node

Answer 1

Path from root to node

Question 2

What is the height of a node

Answer 2

Longest path from node to any connecting leaf

Question 3

What is the depth of a tree

Answer 3

Longest path from root to any leaf

Question 4

What is a full tree

Answer 4

Every node has 0 or 2 children

Question 5

What is the average depth of a binary tree

Answer 5

sqrt(N)

Question 6

What is the time complexity of insert in BST and why

Answer 6

O(n) because it might be unbalanced (lop-sided)

Question 7

What is the rule of an AVL tree

Answer 7

Left and right subtrees may only differ in height by 1 max

Question 8

When do you do a single and a double rotation for AVL trees

Answer 8

Single when imbalance is on the outside and double when inside

Question 9

What are Splay trees

Answer 9

Every node accessed is changed to the root

Question 10

What is complexity of Splay tree operation

Answer 10

worst cast o(n), amortized o(logn)

Question 11

which splay operation is the same as which AVL operation

Answer 11

zig-zag = double rotation