Binary Search Tree

Question 1

Binary Search Tree

Answer 1

• A binary tree that has the following 2 conditions
  
  1. ​root >= all nodes on the left
  2. root < all nodes on the right
• ​Usually implemented with nodes/pointers
• Used to implement sets

Question 2

BST

Insert

Answer 2

• Inserted value always becomes leaf

Steps

1. If root is empty (null), update root w/ value
2. ​If element < root, run insert on left child
3. If element > root, run insert on right child
4. 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

Question 3

BST

Find Min/Max

Answer 3

• To find min (max), recursively go left (right)

Steps

1. If root’s left child is null, return root
2. Othewise, run BST on left child
3. Keep going until root’s left child is null
4. * (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

Question 4

BST

Delete

Answer 4

• Delete varies depending on status of node

Steps

1. If target < root, set left-subtree = delete(root.left)
2. If target > root, set right-subtree = delete(root.right)
3. (If target != root, and children aren’t available, return ‘Target not found’)
4. If target == root, then…
5. If root has no children, return null
6. If root has 1 child, return that child (left or right)
7. If node has 2 children, then…
   
   1. Store value of node
   2. Find-min of right subtree
   3. Copy min into node
   4. 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

Question 5

BST

Print Items in Order

Answer 5

• Use in order traversal

Complexity

Time

Average ⇔ Worst: O(n)

Space

O(1)

Question 6

BST

Verification

Answer 6

• Compare each node to its maximum or minimum allowable value

Steps

1. If node is null, return True
2. If node value < min or > max, return False
   
   • Initial min is -inf, initial max is inf
3. Perform verify on left and right subtrees
4. Where max of left-subtree is node-val - 1, and min of right-subtree is node-val + 1
5. Logical AND results from both subtrees and return boolean value

Complexity

Time

Average ⇔ Worst: O(n)

Space

O(1)

Question 7

Predecessor/Successor

what is it?

Answer 7

• 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

Question 8

Predecessor/Successor

(no subtree)

Answer 8

• 3 approaches (successor)

1. Use parent pointers
   
   1. Loop towards root, starting from node x
   2. Find first parent that is greater than x
2. Use parent pointers
   
   1. Loop towards root, starting from node x
   2. Designate pointers to a trav node and parent node
   3. Find first parent that trav is left child of (i.e. trav is less than)
3. Use root node
   
   1. Loop towards node x, starting from root
   2. Find deepest node greater than x
   3. Stop when you reach x

Question 9

BST - Tree Size

Answer 9

• 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)

Question 10

BST - Rank

Answer 10

• 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]:

1. ​If you go left, add nothing
2. If you go right
   
   1. Add size of left subtree you just passed
   2. Plus 1 for the element you just visited
3. When you reach target, add target’s left subtree

Question 11

BST

Traversal

Answer 11

• 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