binary search trees

bst def

left < root < right

insert in bst

recursively go left/right until null, then insert

are duplicates allowed in a bst

generally NO.

worst case height of bst (big o)

o(n) - tree is skewed

best case height of bst

o(log n) - tree is level, balanced

in order traversal

left - root - right

pre order

root - left - right

post order

left - right - root

level order

breadth first using a queue

delete leaf node - how

just remove it

delete node with one child

replace with the child. corrupt them all.

delete node with two children

replace with in order successor/predecessor

successor is more common

does NOT make any difference

in order successor

smallest node in RIGHT subtree

in order predecessor

largest node in LEFT subtree

what if forget to return the modified subtree on delete/insert

tree doesnt update, logic silently farts in the wind

how is traversal different from structure

traversal visits nodes

visit definition

perform an action on a node—print, remove, etc.

does inserting count as visiting

NO!! what u gana visit if there is no node yet vro 💔💔

recursive insert returns?

new subtree root

deletion time complexity

o(h), h = tree height

does insertion rebalance a bst

no, can become skewed if data is unbalanced

in order traversal always returns?

sorted values (ascending)

In deletion, what does a 2-child case reduce to?

A 1-child or leaf node case (after replacing value)

What happens if you forget to check for null before recursive call?

NullPointerException

Can you use predecessor instead of successor when deleting?

Yes — either keeps the BST valid

Are left and right subtrees of a BST also BSTs?

Yes, by definition

What is the base case for a recursive BST insert?

curNode == null

full tree def

every node has either 0 or 2 children

perfect tree def

all internal nodes have 2 children and all leaf nodes are on the same level (fully filled out)

complete

every level is perfect except for last

last level must be far left as possible

are perfect trees ALWAYS full? are they ALWAYS complete?

by definition yes