Binary Search Tree
- A binary tree that has the following 2 conditions
- root >= all nodes on the left
- root < all nodes on the right
- Usually implemented with nodes/pointers
- Used to implement sets
BST
Insert
- Inserted value always becomes leaf
Steps
- If root is empty (null), update root w/ value
- If element < root, run insert on left child
- If element > root, run insert on right child
- Keep going until node is empty (leaf); then update node with value
Complexity
Time
Average: O(log n) ♦ Worst: O(n)
Space
O(1)
*Worst case occurs when tree is severly imbalanced (devolves to linked list)
*n is the number of nodes
BST
Find Min/Max
- To find min (max), recursively go left (right)
Steps
- If root’s left child is null, return root
- Othewise, run BST on left child
- Keep going until root’s left child is null
- * (Same algorithm applies on the right to finding max)
Complexity
Time
Average: O(log n) ♦ Worst: O(n)
Space
O(1)
*Worst case occurs when tree is severly imbalanced (devolves to linked list)
*n is the number of nodes
BST
Delete
- Delete varies depending on status of node
Steps
- If target < root, set left-subtree = delete(root.left)
- If target > root, set right-subtree = delete(root.right)
- (If target != root, and children aren’t available, return ‘Target not found’)
- If target == root, then…
- If root has no children, return null
- If root has 1 child, return that child (left or right)
- If node has 2 children, then…
- Store value of node
- Find-min of right subtree
- Copy min into node
- Delete min of right subtree
Complexity
Time
Average: O(log n) ♦ Worst: O(n)
Space
O(1)
*Worst case occurs when tree is severly imbalanced (devolves to linked list)
*n is the number of nodes
BST
Print Items in Order
- Use in order traversal
Complexity
Time
Average ⇔ Worst: O(n)
Space
O(1)
BST
Verification
- Compare each node to its maximum or minimum allowable value
Steps
- If node is null, return True
- If node value < min or > max, return False
- Initial min is -inf, initial max is inf
- Perform verify on left and right subtrees
- Where max of left-subtree is node-val - 1, and min of right-subtree is node-val + 1
- Logical AND results from both subtrees and return boolean value
Complexity
Time
Average ⇔ Worst: O(n)
Space
O(1)
Predecessor/Successor
what is it?
- in-order predecessor/successor
- the node that would appear immediately before/after node in in-order traversal
- The predecessor is
- a. the max element in left subtree (if subtree exists)
- b. the first parent (from bottom) that is less than node
- The successor is
- the minimum element of the right subtree (if subtree exists)
- the first parent (from the bottom) that is greater than node
Predecessor/Successor
(no subtree)
- 3 approaches (successor)
- Use parent pointers
- Loop towards root, starting from node x
- Find first parent that is greater than x
- Use parent pointers
- Loop towards root, starting from node x
- Designate pointers to a trav node and parent node
- Find first parent that trav is left child of (i.e. trav is less than)
- Use root node
- Loop towards node x, starting from root
- Find deepest node greater than x
- Stop when you reach x
BST - Tree Size
- Number of elements in a (sub)tree
- Number of element in left sub + right sub + 1
- Should be updated during insertion and deletion operations
- Necessary to compute rank in O(h)
BST - Rank
- The “index “of an item in a BST
- Number of elements with a smaller key
- Naive approach is inorder traveral
- O(log n) approach uses tree sizes
- Should “augment” BST, update size of each subtree during insert/delete operations
Steps - [While searching for node]:
- If you go left, add nothing
- If you go right
- Add size of left subtree you just passed
- Plus 1 for the element you just visited
- When you reach target, add target’s left subtree
BST
Traversal
- Depth First Search
- Preorder
- Inorder
- Postorder
- Breadth First Search
- Also know as level order traversal
- Use a queue
- Works just like BFS does in a graph
