Binary Search Tree

y.key < x.key < z.key

BST Property:
(left < root < right)

two

every node has at most __ children

1. key

2. left

3. right

4. parent

node structure includes:
1.
2.
3.
4.

min key

leftmost node

max key

rightmost node

recursively search left

if k < root.key, …

recursively search right

if k > root.key, …

successor

node with a key just larger (next inorder traversal)

successor case 1

min in right subtree

successor case 2

first ancestor “on the right”

predecessor

node with key just smaller

O(h)

space complexity for BST is __ time

z with key k

Insertion is node ___

(insertion position is where k is expected to be found)

x

deletion is node __

deletion case 1

x is a leaf (just remove x)

deletion case 2

x has one child (splice/connect parent to child)

deletion case 3

x has 2 children (swap x with successor, then delete)

O(log n)

O(n)

Best Case: ____

Worst Case:___

1. root

2. left

3. right

preorder traversal is
1.
2.
3.

1. left

2. root

3. right

inorder traversal is
1.
2.
3.

1. left

2. right

3. root

postorder traversal is
1.
2.
3.