Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

BST Operations: Delete, Validate and Walk in Order

Editorial

Keep the inorder sorted, or read it

The inorder of a binary search tree is its values in sorted order, and every operation in this lesson either keeps that true or reads it. Deleting a node must leave the inorder sorted, so the node that takes its place is its neighbour in that order. Validating a tree checks that the order holds everywhere. The kth smallest value, the next value after a node, and an iterator all read the inorder one step at a time:

Two trees side by side. Left: `[50, 30, 70, 20, 40, 60, 80, null, null, 35, 45]` with 30 marked for deletion and the leftmost node of its right subtree, 35, ringed in green with a curved arrow up to 30. Right: the same tree after the delete, 35 where 30 was. Under each, the inorder: 20 30 35 40 45 50 60 70 80, then 20 35 40 45 50 60 70 80, still sorted.

Deleting a node

First find the node, the same walk as a search. Then there are three cases:

  • No children. It goes; its parent's link becomes empty.
  • One child. The child takes its place, with its whole subtree. Everything in that subtree was already on the correct side of every ancestor, so the order holds.
  • Two children. Neither child can simply move up: each has a subtree of its own. The value that can take its place is its neighbour in the inorder, the next value up. That's the leftmost node of its right subtree, the successor: bigger than everything on the left, smaller than everything else on the right. Copy it in, then delete it from the right subtree; it has no left child, so that's one of the first two cases.
// Delete key from this subtree and return its new root.
TreeNode* deleteNode(TreeNode* root, int key) {
    if (root == nullptr) return nullptr;
    if (key < root->val) root->left = deleteNode(root->left, key);
    else if (key > root->val) root->right = deleteNode(root->right, key);
    else {
        if (root->left == nullptr) return root->right;     // at most one child: it takes the node's place
        if (root->right == nullptr) return root->left;
        TreeNode* next = root->right;                      // two children: the next value up, the successor,
        while (next->left != nullptr) next = next->left;   // is the leftmost node on the right
        root->val = next->val;                             // it takes this node's place
        root->right = deleteNode(root->right, next->val);  // and leaves the right subtree
    }
    return root;
}

def delete_node(root, key):
    """Delete key from this subtree and return its new root."""
    if root is None:
        return None
    if key < root.val:
        root.left = delete_node(root.left, key)
    elif key > root.val:
        root.right = delete_node(root.right, key)
    else:
        if root.left is None:                     # at most one child: it takes the node's place
            return root.right
        if root.right is None:
            return root.left
        nxt = root.right                          # two children: the next value up, the successor,
        while nxt.left is not None:               # is the leftmost node on the right
            nxt = nxt.left
        root.val = nxt.val                        # it takes this node's place
        root.right = delete_node(root.right, nxt.val)   # and leaves the right subtree
    return root

// Delete key from this subtree and return its new root.
static TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;
    if (key < root.val) root.left = deleteNode(root.left, key);
    else if (key > root.val) root.right = deleteNode(root.right, key);
    else {
        if (root.left == null) return root.right;          // at most one child: it takes the node's place
        if (root.right == null) return root.left;
        TreeNode next = root.right;                        // two children: the next value up, the successor,
        while (next.left != null) next = next.left;        // is the leftmost node on the right
        root.val = next.val;                               // it takes this node's place
        root.right = deleteNode(root.right, next.val);     // and leaves the right subtree
    }
    return root;
}

// Delete key from this subtree and return its new root.
function deleteNode(root, key) {
    if (root === null) return null;
    if (key < root.val) root.left = deleteNode(root.left, key);
    else if (key > root.val) root.right = deleteNode(root.right, key);
    else {
        if (root.left === null) return root.right;         // at most one child: it takes the node's place
        if (root.right === null) return root.left;
        let next = root.right;                             // two children: the next value up, the successor,
        while (next.left !== null) next = next.left;       // is the leftmost node on the right
        root.val = next.val;                               // it takes this node's place
        root.right = deleteNode(root.right, next.val);     // and leaves the right subtree
    }
    return root;
}

Each printed the three examples of Delete Node in a BST, then the first example's tree with its root deleted: [5, 4, 6, 2, null, null, 7] after deleting 3, the tree unchanged for 0, which isn't there, [] for an empty tree, and [6, 3, 7, 2, 4] after deleting the root 5, with 6 moved up. The walk down is O(h), and so is the walk to the successor. Step through it:

Deleting 30, which has two children — Indigo is the node being deleted; amber, the walk to its successor; green, the successor.

The predecessor, the rightmost node of the left subtree, works too. Any other value breaks the order somewhere; try one below.

Now you delete

Below, click a node to delete it. With one child, click the node that takes its place; with two, pick the replacement yourself. A choice that would break the order is refused, and the two values it would put in the wrong order light up. The inorder under the tree keeps a cell for every value, a deleted one dimmed: each delete takes one value out and moves nothing else.

Delete a Node: choose what takes each deleted node's place

Validating: ranges, not children

Validate Binary Search Tree asks whether the rule holds. Checking each node against its children isn't enough, as Introduction to Binary Search Trees showed with [5, 3, 8, 1, 6]: 6 is above its parent 3, but it's in 5's left subtree. What a node must satisfy is a range, set by all its ancestors: going left, the parent becomes the new upper bound; going right, the new lower bound:

The tree `[5, 3, 8, 1, 6]` with a range written under each node: any for 5, below 5 for 3, above 5 for 8, below 3 for 1, and 3 to 5 for 6. 6 is red: it's above 3, which its parent allows, but not below 5.
// Every node must sit strictly inside the range its ancestors allow. 64-bit bounds start past any int.
bool valid(TreeNode* node, long long low, long long high) {
    if (node == nullptr) return true;
    if (node->val <= low || node->val >= high) return false;
    return valid(node->left, low, node->val) && valid(node->right, node->val, high);
}

bool isValidBST(TreeNode* root) { return valid(root, LLONG_MIN, LLONG_MAX); }

def is_valid_bst(root):
    """Every node must sit strictly inside the range its ancestors allow."""
    def valid(node, low, high):
        if node is None:
            return True
        if not low < node.val < high:
            return False
        return valid(node.left, low, node.val) and valid(node.right, node.val, high)

    return valid(root, float("-inf"), float("inf"))

// Every node must sit strictly inside the range its ancestors allow. 64-bit bounds start past any int.
static boolean valid(TreeNode node, long low, long high) {
    if (node == null) return true;
    if (node.val <= low || node.val >= high) return false;
    return valid(node.left, low, node.val) && valid(node.right, node.val, high);
}

static boolean isValidBST(TreeNode root) { return valid(root, Long.MIN_VALUE, Long.MAX_VALUE); }

// Every node must sit strictly inside the range its ancestors allow.
function isValidBST(root) {
    const valid = (node, low, high) => {
        if (node === null) return true;
        if (node.val <= low || node.val >= high) return false;
        return valid(node.left, low, node.val) && valid(node.right, node.val, high);
    };
    return valid(root, -Infinity, Infinity);
}

Each printed true false false true true: the problem's two examples, the tree above, and single nodes at the very ends of the int range. The bounds start beyond any int (64 bits in C++ and Java, infinities in Python and JavaScript), because a node can hold -2^31 or 2^31 - 1 itself. Step through the check:

Checking the ranges — Each badge is the range that node must sit in; violet, checked; red, outside its range.

An equivalent check: the inorder must be strictly increasing. Walk it, and compare each value with the one before.

The inorder, one step at a time

Binary Search Tree Iterator hands out the values in sorted order, one per next(), using O(h) memory, not a list of all n. Keep a stack of the left spine of what's still to come: start with the root's left spine; next() pops the smallest, then pushes the left spine of its right child, the values between it and its ancestors:

// The inorder one step at a time: the stack holds the left spine of what's still to come, at most h nodes.
class BSTIterator {
    stack<TreeNode*> spine;
    void pushLeft(TreeNode* node) {
        for (; node != nullptr; node = node->left) spine.push(node);
    }

public:
    BSTIterator(TreeNode* root) { pushLeft(root); }
    int next() {
        TreeNode* node = spine.top();
        spine.pop();
        pushLeft(node->right);                // the values after node, before its ancestors, are on its right
        return node->val;
    }
    bool hasNext() { return !spine.empty(); }
};

class BSTIterator:
    """The inorder one step at a time: the stack holds the left spine of what's still to come, at most h nodes."""

    def __init__(self, root):
        self.spine = []
        self._push_left(root)

    def _push_left(self, node):
        while node is not None:
            self.spine.append(node)
            node = node.left

    def next(self):
        node = self.spine.pop()
        self._push_left(node.right)           # the values after node, before its ancestors, are on its right
        return node.val

    def has_next(self):
        return bool(self.spine)

// The inorder one step at a time: the stack holds the left spine of what's still to come, at most h nodes.
static class BSTIterator {
    private final Deque<TreeNode> spine = new ArrayDeque<>();

    BSTIterator(TreeNode root) { pushLeft(root); }

    private void pushLeft(TreeNode node) {
        for (; node != null; node = node.left) spine.push(node);
    }

    public int next() {
        TreeNode node = spine.pop();
        pushLeft(node.right);                 // the values after node, before its ancestors, are on its right
        return node.val;
    }

    public boolean hasNext() { return !spine.isEmpty(); }
}

// The inorder one step at a time: the stack holds the left spine of what's still to come, at most h nodes.
class BSTIterator {
    constructor(root) {
        this.spine = [];
        this.pushLeft(root);
    }
    pushLeft(node) {
        for (; node !== null; node = node.left) this.spine.push(node);
    }
    next() {
        const node = this.spine.pop();
        this.pushLeft(node.right);            // the values after node, before its ancestors, are on its right
        return node.val;
    }
    hasNext() {
        return this.spine.length > 0;
    }
}

Each printed 3 7 true 9 true 15 true 20 false for the problem's example. Every node is pushed once and popped once, so a whole walk is O(n), O(1) per call on average, and the stack never holds more than one node per level.

The same loop answers Kth Smallest Element in a BST: pop k times and stop.

def kth_smallest(root, k):
    """The inorder, stopped at its kth value."""
    spine, node = [], root
    while True:
        while node is not None:
            spine.append(node)
            node = node.left
        node = spine.pop()
        k -= 1
        if k == 0:
            return node.val
        node = node.right

On [50, 30, 70, 20, 40, 60, 80, null, null, 35, 45] the 1st smallest is 20 and the 4th is 40. Stopping matters when k is small. On a random tree of 100,000 values (height 38):

kThe whole inorder, then index kStopping after k values
148.0 ms0.002 ms
50,00048.4 ms22.528 ms

Inorder Successor in BST asks for the value right after p in the inorder. It's the smallest value bigger than p: a ceiling, without equality, so walk down from the root keeping the best candidate:

def inorder_successor(root, p):
    """The smallest value bigger than p: like a ceiling, a node above p is a candidate, and a smaller one is on its left."""
    best, node = None, root
    while node is not None:
        if p.val < node.val:
            best, node = node, node.left
        else:
            node = node.right
    return best

In [50, 30, 70, 20, 40, 60, 80, null, null, 35, 45] the successors of 45, 35 and 80 came out 50 40 none: 80 is the largest, so nothing comes after it.

Two Sum, and the lowest common ancestor by value

Two Sum IV - Input is a BST asks whether two values add up to k. The inorder is sorted, so the two-pointer scan from Two Pointers finds a pair in one pass:

def find_target(root, k):
    """The inorder is sorted, so two pointers from its ends meet any pair that adds up to k."""
    values = []

    def inorder(node):
        if node is not None:
            inorder(node.left)
            values.append(node.val)
            inorder(node.right)

    inorder(root)
    lo, hi = 0, len(values) - 1
    while lo < hi:
        total = values[lo] + values[hi]
        if total == k:
            return True
        if total < k:
            lo += 1
        else:
            hi -= 1
    return False

In Two Sum IV's tree it said True False for 9 and 28. A set of the values seen while walking works too, in O(n) time and space, on any tree.

Lowest Common Ancestor of a Binary Search Tree doesn't need the general recursion from Views, Ancestors and Distances. While both values are smaller than the node, the answer is on the left; while both are bigger, on the right; the first node that splits them, or is one of them, is the answer:

// Both values on the same side: go there. Otherwise this node splits them, and it's the answer.
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    TreeNode* node = root;
    while (true) {
        if (p->val < node->val && q->val < node->val) node = node->left;
        else if (p->val > node->val && q->val > node->val) node = node->right;
        else return node;
    }
}

def lowest_common_ancestor(root, p, q):
    """Both values on the same side: go there. Otherwise this node splits them, and it's the answer."""
    node = root
    while True:
        if p.val < node.val and q.val < node.val:
            node = node.left
        elif p.val > node.val and q.val > node.val:
            node = node.right
        else:
            return node

// Both values on the same side: go there. Otherwise this node splits them, and it's the answer.
static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    TreeNode node = root;
    while (true) {
        if (p.val < node.val && q.val < node.val) node = node.left;
        else if (p.val > node.val && q.val > node.val) node = node.right;
        else return node;
    }
}

// Both values on the same side: go there. Otherwise this node splits them, and it's the answer.
function lowestCommonAncestor(root, p, q) {
    let node = root;
    while (true) {
        if (p.val < node.val && q.val < node.val) node = node.left;
        else if (p.val > node.val && q.val > node.val) node = node.right;
        else return node;
    }
}

Each printed 6 2 2: 2 and 8 split at the root 6, 4 is below 2 and 2 counts as its own ancestor, and in [2, 1] the answer is 2. One walk down, O(h), and no recursion.

Building from preorder, recovering, and the largest BST

Construct Binary Search Tree from Preorder Traversal: inserting each value works, at O(h) each. Bounds do it in one pass: the next value is the root of what follows, the values smaller than it make its left subtree, and the rest, up to its own bound, its right:

def bst_from_preorder(preorder):
    """Each value is the root of what follows it, up to the first value bigger than its bound."""
    i = 0

    def build(high):
        nonlocal i
        if i == len(preorder) or preorder[i] > high:
            return None
        node = TreeNode(preorder[i])
        i += 1
        node.left = build(node.val)               # what follows, while it's smaller than the node
        node.right = build(high)                  # then the rest, up to the node's own bound
        return node

    return build(float("inf"))

It built [8, 5, 10, 1, 7, null, 12] from the problem's [8, 5, 1, 7, 10, 12]. On a sorted preorder, a chain, inserting costs O(n²):

PreorderInserting each valueWith bounds
1,000 sorted36.1 ms1.13 ms
2,000 sorted142.2 ms2.22 ms
4,000 sorted567.8 ms5.10 ms
4,000 random7.1 ms4.51 ms

Recover Binary Search Tree: two values were swapped by mistake. In the inorder, a swap leaves a drop, a value bigger than the one after it. Swapped neighbours leave one drop; values further apart leave two. The first wrong value is the bigger side of the first drop, the second is the smaller side of the last drop:

Two inorder sequences. Top: 1 3 2 4, from swapping the neighbours 2 and 3, with one drop between 3 and 2. Bottom: 1 7 3 4 5 2 8, from swapping 2 and 7, with two drops, 7 to 3 and 5 to 2. In each, the two values to swap back are ringed: the first drop's bigger side and the last drop's smaller side.
def recover_tree(root):
    """Two values were swapped: the inorder drops once (neighbours swapped) or twice. Fix the two ends."""
    first = second = prev = None
    stack, node = [], root
    while stack or node:
        while node is not None:
            stack.append(node)
            node = node.left
        node = stack.pop()
        if prev is not None and prev.val > node.val:
            if first is None:
                first = prev                      # the bigger side of the first drop
            second = node                         # the smaller side of the last drop
        prev, node = node, node.right
    first.val, second.val = second.val, first.val

It repaired the problem's two examples to [3, 1, null, null, 2] and [2, 1, 4, null, null, 3]; the second has neighbours swapped, one drop. O(n) time and O(h) for the stack.

Largest BST Subtree: the biggest subtree that's a binary search tree. Checking every subtree on its own repeats work. Instead, each call returns whether its subtree is one, its smallest and largest value, and its size; a subtree is one exactly when both its children's subtrees are, the left's largest is below its root, and the right's smallest above it:

def largest_bst_subtree(root):
    """Each call returns (is a BST, smallest, largest, size): its children's answers decide it in O(1)."""
    best = 0

    def go(node):
        nonlocal best
        if node is None:
            return True, float("inf"), float("-inf"), 0
        l_ok, l_min, l_max, l_size = go(node.left)
        r_ok, r_min, r_max, r_size = go(node.right)
        if l_ok and r_ok and l_max < node.val < r_min:
            size = l_size + r_size + 1
            best = max(best, size)
            return True, min(l_min, node.val), max(r_max, node.val), size
        return False, 0, 0, 0

    go(root)
    return best

It returned 3 for [10, 5, 15, 1, 8, null, 7]: the subtree 5, 1, 8. On a BST with one leaf broken:

NodesChecking every subtreeOne postorder
1,0006.6 ms1.21 ms
2,00015.7 ms2.44 ms
4,00034.0 ms5.02 ms

Spotting it, and when it breaks

The clues. "Delete", "remove" from a BST: the three cases, the successor for two children. "Valid", "is it a BST": ranges passed down, or an increasing inorder. "Kth smallest", "next", "in sorted order", "iterator": the inorder with a stack, stopped early. "Swapped", "recover": the drops in the inorder. "Largest" or "count" of BST subtrees: a postorder returning facts about each subtree.

The near-misses. The lowest common ancestor in a plain binary tree has no order to use (Views, Ancestors and Distances). Building from preorder and inorder needs the inorder only because a plain tree has no order (Building and Serializing Trees). The kth smallest of an array, with no tree, is a heap or quickselect (Heaps).

When it breaks. The walks down cost the height, and a chain makes that n; recursion on a chain runs out of stack in Python. Duplicates need a rule (left, right, or a count) before delete and validate mean anything.

Bugs that cost a submission

Checking only the children.

def is_valid_bst(node):
    if node is None:
        return True
    if node.left is not None and node.left.val >= node.val:
        return False                              # only the children are checked
    if node.right is not None and node.right.val <= node.val:
        return False
    return is_valid_bst(node.left) and is_valid_bst(node.right)

On [5, 3, 8, 1, 6] it said True; the answer is false. Pass the range down.

Int sentinels for the bounds (C++ and Java).

bool valid(TreeNode* node, int low, int high) {
    if (node == nullptr) return true;
    if (node->val <= low || node->val >= high) return false;
    return valid(node->left, low, node->val) && valid(node->right, node->val, high);
}

bool isValidBST(TreeNode* root) { return valid(root, INT_MIN, INT_MAX); }

For the single node -2147483648 it said false: the node equals the starting low bound, and a strict check rejects it. Start the bounds beyond any int.

Copying the successor without removing it.

def delete_node(root, key):
    """Delete key from this subtree and return its new root."""
    if root is None:
        return None
    if key < root.val:
        root.left = delete_node(root.left, key)
    elif key > root.val:
        root.right = delete_node(root.right, key)
    else:
        if root.left is None:                     # at most one child: it takes the node's place
            return root.right
        if root.right is None:
            return root.left
        nxt = root.right                          # two children: the next value up, the successor,
        while nxt.left is not None:               # is the leftmost node on the right
            nxt = nxt.left
        root.val = nxt.val                        # it takes this node's place
    return root

Deleting 5 from [5, 3, 6, 2, 4, null, 7] gave [6, 3, 6, 2, 4, null, 7]: 6 moved up, and stayed below as well. Delete it from the right subtree after copying.

Handling only the two-drop case.

def recover_tree(root):
    drops, prev, stack, node = [], None, [], root
    while stack or node:
        while node is not None:
            stack.append(node)
            node = node.left
        node = stack.pop()
        if prev is not None and prev.val > node.val:
            drops.append((prev, node))
        prev, node = node, node.right
    if len(drops) == 2:                           # only the case of two drops
        drops[0][0].val, drops[1][1].val = drops[1][1].val, drops[0][0].val

On [3, 1, 4, null, null, 2], where the neighbours 2 and 3 were swapped, the tree came back unchanged as [3, 1, 4, null, null, 2]: one drop, and the code only handles two. The second value is the smaller side of the last drop, which can be the first.

Check yourself

Quiz

1 / 6

Multiple choice

With this lesson's delete, you remove 50, the root of [50, 30, 70, 20, 40, 60, 80, null, null, 35, 45]. Which value takes its place?

Practice problems

In this order:

  1. Delete Node in a BST: three cases, the successor for two children.
  2. Validate Binary Search Tree: ranges passed down.
  3. Kth Smallest Element in a BST: the inorder, stopped early.
  4. Inorder Successor in BST: a ceiling, without equality.
  5. Binary Search Tree Iterator: the left spine on a stack.
  6. Two Sum IV - Input is a BST: the sorted inorder and two pointers.
  7. Lowest Common Ancestor of a Binary Search Tree: walk down until the values split.
  8. Construct Binary Search Tree from Preorder Traversal: bounds.
  9. Recover Binary Search Tree: one drop or two.
  10. Largest BST Subtree: a postorder that returns four facts.

Next, Balanced Trees and Ordered Sets: the trees that stay short, and the ones your language gives you.