trees

Question 1

trees store items _________

Answer 1

hierarchically

Question 2

leaf or external node

Answer 2

node with no children

Question 3

internal node

Answer 3

has one or more children

Question 4

depth of a node

Answer 4

the length of the path from that node to the root

Question 5

height of a node

Answer 5

the length of the longest path from that node to a leaf

Question 6

ways of implementing a tree

Answer 6

1. using an array
2. pointer-based

Question 7

downside of array tree implementation

Answer 7

inefficient when it comes to locating the children of a node

Question 8

array and pointer-based approach both require ________________ amount of space

Answer 8

asymptotically the same

Question 9

trie or prefix tree

Answer 9

simple and practically fast data structure that implements the dictionary adts

Question 10

running time for dictionary operations in a trie

Answer 10

O(n)

Question 11

binary trees

Answer 11

each node has at most two children

Question 12

a binary tree is full

Answer 12

if all internal nodes have 2 children

Question 13

nL(T) =

Answer 13

nI(T) + 1

Question 14

maximum size of a BST of size n

Answer 14

n-1

Question 15

minimum size of a BST of size n

Answer 15

log(n+1)-1

Question 16

Catalan number is __ than n!

Answer 16

smaller

Question 17

expected height of a binary search tree

Answer 17

O(logn)

Question 18

AVL trees

Answer 18

height-balanced property: for every internal node the height difference between children is at most 1

Question 19

height of an AVL tree storing n keys

Answer 19

O(logn)