# binary search trees Flashcards

additional properties of BST

nodes can be compared by some value

nodes on the left are less that node

nodes on the right are greater than node - can also define one side as equals

advant and disadvantages of BST

faster search

more work when adding/removing nodes

BST insert algorithm

if root = null –> new node becomes entire tree

value node add new node to RHS

recured until the node gets added as a new leaf node - nodes are only added as new leaf nodes

BST find algorithm

start at root

- if search == root return root
- if searchroot recurse into RHS subtree

delete algorithm

find element to delete - if element is a leaf - just delete - 1 child - replace node with its child - 2 children \+++ find x = min node in RHS subtree \+++ remove x from RHS subtree \+++ replace deleted element with x

how to handle duplicate keys

assume all keys are unique

- issue:

++is it identical items copies or different items with identical identifier keys

options =

++ duplicates in adjacent tree positions - modify all operations to deal with this

++ counter for dupes

++list of items attached to each node

complexity analysis for operations (find insert delete)

best case - O(1)

worst case -O(n)

why is the worst case not O(log n )

the tree could be linear in shape

things to go over and add

- little o notations
- findK
- level order traversals explanations

height

maximum edges from root to leaf

size

number of nodes

level

number of rows h+1

full tree

no single child nodes

complete tree-

has minimum height

all levels have every node except last and last is filled from left to right

balanced tree

nodes are distributed according to some balancing factor