Binary Search Tree Flashcards

1
Q

Binary Search Tree

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

BST

Insert

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

BST

Find Min/Max

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

BST

Delete

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

BST

Print Items in Order

A
  • Use in order traversal

Complexity

Time

Average ⇔ Worst: O(n)

Space

O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

BST

Verification

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Predecessor/Successor

what is it?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Predecessor/Successor

(no subtree)

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

BST - Tree Size

A
  • 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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

BST - Rank

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

BST

Traversal

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly