Search trees and the ordering you can exploit

Three problems that all collapse once you take the ordering property seriously.

Key idea

The property, stated carefully

In a binary search tree, everything in a node's left subtree is smaller than the node, and everything in its right subtree is larger. Note the word everything: the promise is about entire subtrees, not just about immediate children.

That distinction is the source of the most common wrong answer in this whole unit, and the validation problem below is built on it.

1class T:2    def __init__(self, val, left=None, right=None):3        self.val, self.left, self.right = val, left, right4 5# Every parent-child pair is correctly ordered, and this is NOT a search6# tree: 12 sits inside the root's left subtree while being larger than 10.7tree = T(10, T(5, T(1), T(12)), T(15))8print(tree.left.val < tree.val)          # 5 is correctly left of 109print(tree.left.right.val > tree.left.val)   # 12 is correctly right of 510print(tree.left.right.val < tree.val)    # but 12 is not below 10

Why it works

Validation carries a range downward

Checking each node against its children is not enough. Each node must be checked against a range of values it is allowed to hold, and that range narrows as you descend.

The root may hold anything. Moving left tightens the upper bound to the parent's value; moving right tightens the lower bound. This is the carry-down pattern from the last lesson, with two pieces of context instead of one.

Below, the narrowing is done along one chosen path rather than over the whole tree, so that the window itself is the thing on display.

1class T:2    def __init__(self, val, left=None, right=None):3        self.val, self.left, self.right = val, left, right4 5def window_along_path(root, directions):6    """Follow a path and report the window the node landed on must sit in."""7    low, high = None, None8    node = root9    for step in directions:10        if step == "L":11            high = node.val              # everything left of here is below it12            node = node.left13        else:14            low = node.val               # everything right of here is above it15            node = node.right16    return node.val, low, high17 18tree = T(10, T(5, T(1), T(12)), T(15))19print(window_along_path(tree, "L"))20print(window_along_path(tree, "LL"))21print(window_along_path(tree, "LR"))

The last line is the violation: 12 has to be under 10, and it is not.

Key idea

Searching takes one path, not a traversal

The ordering means a search never has to look at both children. Compare the target with the node and descend into the only side that could contain it.

That is O(h) rather than O(n), and h is about log n for a balanced tree. Any BST problem where you find yourself traversing everything deserves a second look, because the ordering usually rules out most of the tree.

1class T:2    def __init__(self, val, left=None, right=None):3        self.val, self.left, self.right = val, left, right4 5def contains(node, target):6    while node:7        if target == node.val:8            return True9        node = node.left if target < node.val else node.right10    return False11 12tree = T(10, T(5, T(1), T(7)), T(15))13print(contains(tree, 7), contains(tree, 8))

Why it works

In-order traversal is sorted

Visit the left subtree, then the node, then the right subtree, and the values come out in ascending order. That follows directly from the ordering property and it is the single most useful fact about search trees.

It turns questions about rank and order into questions about position in a sorted sequence. The kth smallest value is the kth thing this traversal produces, so the traversal can stop as soon as it has produced k, without visiting the rest.

1class T:2    def __init__(self, val, left=None, right=None):3        self.val, self.left, self.right = val, left, right4 5def in_order(node):6    if node is None:7        return []8    return in_order(node.left) + [node.val] + in_order(node.right)9 10tree = T(10, T(5, T(1), T(7)), T(15))11print(in_order(tree))

Quick check· 5 min

Why is checking children not enough?

A candidate validates a search tree by checking, at every node, that its left child is smaller and its right child is larger. What does this miss?

A node deeper in the left subtree can be larger than an ancestor while still being correctly placed relative to its own parentNothing; if every parent-child pair is ordered then the whole tree is orderedIt fails only when the tree contains duplicate valuesIt fails only on unbalanced trees

Problem· 22 min

Validate Binary Search Tree

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Problem· 20 min

Lowest Common Ancestor Of A Binary Search Tree

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Problem· 22 min

Kth Smallest Element In A Bst

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1class T:2 def __init__(self, val, left=None, right=None):3 self.val, self.left, self.right = val, left, right4 5# Every parent-child pair is correctly ordered, and this is NOT a search6# tree: 12 sits inside the root's left subtree while being larger than 10.7tree = T(10, T(5, T(1), T(12)), T(15))8print(tree.left.val < tree.val) # 5 is correctly left of 109print(tree.left.right.val > tree.left.val) # 12 is correctly right of 510print(tree.left.right.val < tree.val) # but 12 is not below 10

1class T:2 def __init__(self, val, left=None, right=None):3 self.val, self.left, self.right = val, left, right4 5def window_along_path(root, directions):6 """Follow a path and report the window the node landed on must sit in."""7 low, high = None, None8 node = root9 for step in directions:10 if step == "L":11 high = node.val # everything left of here is below it12 node = node.left13 else:14 low = node.val # everything right of here is above it15 node = node.right16 return node.val, low, high17 18tree = T(10, T(5, T(1), T(12)), T(15))19print(window_along_path(tree, "L"))20print(window_along_path(tree, "LL"))21print(window_along_path(tree, "LR"))

1class T:2 def __init__(self, val, left=None, right=None):3 self.val, self.left, self.right = val, left, right4 5def contains(node, target):6 while node:7 if target == node.val:8 return True9 node = node.left if target < node.val else node.right10 return False11 12tree = T(10, T(5, T(1), T(7)), T(15))13print(contains(tree, 7), contains(tree, 8))

1class T:2 def __init__(self, val, left=None, right=None):3 self.val, self.left, self.right = val, left, right4 5def in_order(node):6 if node is None:7 return []8 return in_order(node.left) + [node.val] + in_order(node.right)9 10tree = T(10, T(5, T(1), T(7)), T(15))11print(in_order(tree))