Binary Search Tree Flashcards
1
Q
What numbers go on the left and right of the node?
A
Smaller numbers on the left, bigger numbers on the right.
2
Q
What is the runtime of binary search?
A
log(n)
3
Q
What is the runtime of insert?
A
log(n)
4
Q
What is the runtime of delete?
A
log(n)
5
Q
What is the runtime of findMin?
A
log(n)
6
Q
What is the runtime of findMax?
A
log(n)
7
Q
List the traversals and their order.
A
Pre order: node, left, right
In order: left, node, right
Post order: left, right, node
Breadth: print row by row
8
Q
How to remove a node with no children?
A
Just remove the node since there are no kids.
9
Q
How to remove a node with one child?
A
Give the child value to the parent.
10
Q
How to remove a node with two children?
A
Replace data with the smallest value from the right child. Delete the node on the right.
