Binary Search Trees Checkpoint
A review of this module. Skip it if you feel confident; the next module does not need it.
Fix the mistakes
The slips that cost marks in this module. Spot each one, then check the fix.
This checkpoint mixes everything in the module on order numbers and prices. Read the question, decide whether it is about one path, the sorted order, or a range, then write it.
One path: search, insert, floor, ceiling, delete
These questions follow a single path from the root, choosing left or right by comparing keys. They cost O(h). Floor and ceiling remember the last candidate on the way down.
def floor(root, x): best = None node = root while node is not None: if node.key == x: return x if node.key < x: best = node.key node = node.right else: node = node.left return bestDelete is also one path, plus a second walk for the successor when the node has two children. Always store the result: root = delete(root, key).
The sorted order: inorder, validate, kth
When the question is about order, think of the inorder walk. A tree is a BST when inorder keys strictly increase. The kth smallest is the kth key of the walk, and a generator stops early.
def is_bst(node, low=None, high=None): if node is None: return True if low is not None and node.key <= low: return False if high is not None and node.key >= high: return False return is_bst(node.left, low, node.key) and is_bst(node.right, node.key, high)Example 1 · Order numbers: insert, delete, list
class Node: def __init__(self, key): self.key = key self.left = None self.right = None
def insert(node, key): if node is None: return Node(key) if key < node.key: node.left = insert(node.left, key) elif key > node.key: node.right = insert(node.right, key) return node
def smallest(node): while node.left is not None: node = node.left return node
def delete(node, key): if node is None: return None if key < node.key: node.left = delete(node.left, key) elif key > node.key: node.right = delete(node.right, key) else: if node.left is None: return node.right if node.right is None: return node.left successor = smallest(node.right) node.key = successor.key node.right = delete(node.right, successor.key) return node
def inorder(node): if node is not None: yield from inorder(node.left) yield node.key yield from inorder(node.right)
root = Nonefor order in [105, 102, 110, 101, 104, 108, 120]: root = insert(root, order)root = delete(root, 102)root = delete(root, 120)root = insert(root, 106)print(*inorder(root))print(root.key, root.left.key)101 104 105 106 108 110 105 104
What this code does
- 102 has two children, so 104, the smallest key of its right subtree, takes its place. 120 is a leaf and is removed.
- The inorder list stays sorted after every change, which shows the rule still holds.
Example 2 · Price queries on one tree
class Node: def __init__(self, key): self.key = key self.left = None self.right = None
from collections import deque
def build(tokens): if not tokens or tokens[0] == "#": return None root = Node(int(tokens[0])) queue = deque([root]) rest = iter(tokens[1:]) while queue: node = queue.popleft() for side in ("left", "right"): token = next(rest, "#") if token != "#": child = Node(int(token)) setattr(node, side, child) queue.append(child) return root
def inorder(node): if node is not None: yield from inorder(node.left) yield node.key yield from inorder(node.right)
def floor(root, x): best = None node = root while node is not None: if node.key == x: return x if node.key < x: best = node.key node = node.right else: node = node.left return best
def ceiling(root, x): best = None node = root while node is not None: if node.key == x: return x if node.key > x: best = node.key node = node.left else: node = node.right return best
def keys_in_range(node, low, high): if node is None: return if low < node.key: yield from keys_in_range(node.left, low, high) if low <= node.key <= high: yield node.key if node.key < high: yield from keys_in_range(node.right, low, high)
from itertools import islicedef kth_smallest(root, k): return next(islice(inorder(root), k - 1, None))
root = build("50 30 70 20 40 60 80".split())print(kth_smallest(root, 3))print(floor(root, 55), ceiling(root, 55))print(list(keys_in_range(root, 35, 65)))40 50 60 [40, 50, 60]
What this code does
- The sorted prices are 20, 30, 40, 50, 60, 70, 80, so the third is 40.
- 55 is between 50 and 60. The range 35 to 65 holds 40, 50 and 60.
The bounds version needs no list. Going left, the node's key becomes the high bound. Going right, it becomes the low bound.
Choose the cost and the tool
Every operation here costs O(h). A balanced tree has h of about log n, and a chain has h = n. For static data a sorted list with bisect is simpler, and in an interview you write the BST by hand.
Example 3 · Is it still a BST after a bad edit?
class Node: def __init__(self, key): self.key = key self.left = None self.right = None
from collections import deque
def build(tokens): if not tokens or tokens[0] == "#": return None root = Node(int(tokens[0])) queue = deque([root]) rest = iter(tokens[1:]) while queue: node = queue.popleft() for side in ("left", "right"): token = next(rest, "#") if token != "#": child = Node(int(token)) setattr(node, side, child) queue.append(child) return root
def inorder(node): if node is not None: yield from inorder(node.left) yield node.key yield from inorder(node.right)
from itertools import pairwisedef is_bst(root): keys = list(inorder(root)) return all(a < b for a, b in pairwise(keys))
root = build("50 30 70 20 40 60 80".split())print(is_bst(root))root.left.right.key = 55print(is_bst(root))print(*inorder(root))True False 20 30 55 50 60 70 80
What this code does
- Changing 40 to 55 keeps it larger than its parent 30. But 55 is in the left subtree of 50, so it must be smaller than 50.
- The inorder keys 20, 30, 55, 50, ... are out of order, which proves it.
Module quiz
Questions from the whole module. Your first answer is your score.
Problems
Graded easy to hard, using everything from this module.
Try each one yourself first. Use the hint if you get stuck. Mark it as done when it works.
Exercise 1· Easy
Insert 50, 30, 70, 20, 40, 60, 80, then print the inorder keys, then the height, on two lines.
20 30 40 50 60 70 80 3
Exercise 2· Easy
Print the smallest and largest key of the tree 15 10 20 8 12 17 25 by walking left and right.
8 25
Exercise 3· Easy
Print whether the tree 10 5 15 3 7 12 18 is a BST, using the bounds check.
True
Exercise 4· Medium
Insert 40, 20, 60, 10, 30, 50, 70 then delete 20 and 60. Print the preorder keys.
40 30 10 70 50
Exercise 5· Medium
For the tree 50 30 70 20 40 60 80, print the floor and ceiling of 65, then the sum of keys from 30 to 60, on two lines.
60 70 180
Exercise 6· Medium
Print the 3rd largest key of 50 30 70 20 40 60 80 with a reversed inorder walk.
60
Exercise 7· Hard
Build a balanced tree from the keys 5, 10, 15, 20, 25, 30, 35, 40 and print the preorder keys.
20 10 5 15 30 25 35 40
Exercise 8· Hard
Print the keys of the tree 8 3 10 1 6 # 14 whose value is larger than the average of all keys. Print them in increasing order.
8 10 14
Interview questions
Questions interviewers ask on this topic.
Finish up
Mark complete & continue
Next: Must-do problems: Binary Search Trees