Binary Search Tree (Module 8.2) PART III Flashcards
1
Q
How do you delete a node in BST that doesn’t have any children?
A
return null to the node’s parent
2
Q
How do you delete a node in BST that has one child?
A
replace the node with its only child (left or right)
3
Q
How do you delete a node in BST that has two children?
A
1) Replace the node’s value with its in-order successor or predecessor
2) Recursively delete the in-order successor or predecessor from its original position
4
Q
What is the best case time complexity for BST Deletion?
A
O(log n)
5
Q
What is the worst case time complexity for BST Deletion?
A
O(n)
