Delete and inorder successor in Python

Why it matters

Adding values to a BST is easy, because a new value always fits in one empty spot at the bottom. Removing a value is harder. The node you remove may have children, and those children must stay in the right place. Deleting correctly is the test that separates someone who has memorised a tree from someone who understands it. It is also one of the most common questions in technical interviews.

This lesson teaches the idea of the inorder successor, the value that comes right after a given value in sorted order. The successor is the piece that makes deletion work. By the end you will be able to find it, delete a node in each of the three cases, and check your work with a walk that prints the values in order.

An everyday picture of deleting

Think of a shelf of books sorted by title. You want to take one book off the shelf. If it is at the end, the shelf is still sorted. If it is in the middle, there is now a gap, but the books on either side are still in order, so nothing is broken. The shelf only has a problem if you move a book to the wrong side of another.

A BST is harder because a node is not just a gap on a shelf. It is a parent that points to it, and it may have books hanging underneath it. If you remove the node, every link that used to lead to it must now lead somewhere useful, and the rule must still hold at every node. Deletion is the job of rewiring the links so that the tree still looks like a valid tree.

Look at the tree from the previous lesson:

          50
        /    \
      30      70
     /  \    /  \
   20   40  60   80

Suppose you delete 50, the root. The root has two children, 30 and 70. You cannot simply throw the root away, because 30 and 70 would be disconnected. You need a new root that is larger than everything on the left (20, 30, 40) and smaller than everything on the right (60, 70, 80). The only value that fits is the one that comes right after 50 in sorted order. That value is 60. The inorder successor is the answer.

The inorder successor

The inorder successor of a value v in a BST is the smallest value in the tree that is larger than v. In the sorted list of the tree's values, it is the value that sits immediately after v.

For the tree above, the sorted values are 20, 30, 40, 50, 60, 70, 80. So:

• the successor of 20 is 30,
• the successor of 40 is 50,
• the successor of 50 is 60,
• the successor of 80 does not exist, because 80 is the largest value.

The name comes from the inorder walk, the walk that visits the left subtree, then the node, then the right subtree. In the inorder walk the values come out in sorted order, so the successor is the node that comes next in that walk.

Step through the inorder walk on the tree. Watch the order in which the nodes are marked. The node after 40 is 50, and the node after 50 is 60. That next node is the inorder successor of the node you are looking at.

Why the successor is the right replacement

When you delete a node with two children, you may replace its value with a value that keeps the BST rule. The inorder successor always does. Here is the reason, written as a checklist:

1. The successor is larger than the deleted value. So it is larger than everything in the left subtree of the deleted node, which were all smaller than the deleted value.
2. The successor is the smallest value in the right subtree. So it is no larger than anything else in the right subtree.
3. Once the successor's value is copied into the deleted node's place, the node has the same left subtree as before, and a right subtree that is the same as before except that the successor has been removed from it.
4. The removed successor was the smallest value in the right subtree, so the rest of the right subtree is still larger than the new value.

Each step keeps the rule. The predecessor (the largest value smaller than v) would work too, by the same reasoning on the left side. Pick one and use it consistently, as this lesson does with the successor.

Finding the successor from the root

There is a simple way to find the successor of any value in the tree, even when the value is not stored in the tree. Walk down from the root, just as a search does. Keep a note of the last node where you went left. Every time you go left from a node, that node is larger than your value, so it is a candidate. The last candidate you noted is the answer.

Here is the walk for 40 in the tree from the start of the lesson.

The answer is 50. Now the walk for 60, which is a leaf.

The answer is 70. The successor of 60 is not below it. It is an ancestor, the node 70 that the walk turned left at.

Two things make this method work. It works for any value, even one that is absent. The successor of 45 is 50, because the walk turns left at 50 and then right at 40 and ends. And when the value is the largest, the walk never turns left, so it returns None. That None is the signal that there is no successor, and it must be checked before you read an attribute of it.

The code is short:

def successor(root, v):
    succ = None
    cur = root
    while cur is not None:
        if v < cur.val:
            succ = cur          # bigger than v, maybe the closest so far
            cur = cur.left
        else:
            cur = cur.right     # v or smaller: look right
    return succ

The variable succ is the candidate. The loop runs once per level, so the time is O(h).

The other way: the minimum of the right subtree

There is a second method. If the node has a right subtree, its successor is the smallest value in that subtree, found by going left as far as you can. For 50, the right subtree starts at 70, and going left from 70 reaches 60. For 30, the right subtree is just 40, and 40 has no left child, so the successor of 30 is 40.

If the node has no right subtree, the successor is the nearest ancestor where you turned left on the way down. That is exactly what the root walk above finds. The two methods agree. Deletion uses the first method, because it needs the minimum of a subtree anyway.

The mirror image: the predecessor

The inorder predecessor of a value is the largest value smaller than it. It is the mirror image of the successor. Walk right where the successor walk goes left, keep the last node where you turned right, and you have the answer.

def predecessor(root, v):
    best = None
    cur = root
    while cur is not None:
        if v > cur.val:
            best = cur              # smaller than v, maybe the closest so far
            cur = cur.right
        else:
            cur = cur.left          # v or larger: look left
    return best

Check it on the seven-node tree. For 60, the walk goes to 50 (60 is larger, so 50 is a candidate and the walk goes right), then to 70 (60 is smaller, so the walk goes left), then to 60 (equal, so the walk goes left into None). The last candidate is 50, which is the predecessor. For 40, the walk goes to 50 (go left), then to 30 (40 is larger, so 30 is a candidate and the walk goes right), then to 40 (equal, go left into None). The answer is 30. For 20, every step goes left, no candidate is ever stored, and the answer is None, because 20 is the smallest value.

A delete that uses the predecessor is also correct. In case 3, copy the largest value of the left subtree instead of the smallest of the right subtree, then delete that value from the left subtree. The two methods are equally correct. The rule in this lesson is to pick one and use it everywhere, so that your code is easy to read and test.

Delete: three cases

To delete a value, first find its node. Then look at how many children the node has. There are three cases.

Case 1: a leaf. The node has no children. Remove it by setting its parent's link to None. Nothing else needs to change, because nothing depends on the leaf.

Case 2: one child. The node has exactly one child. Replace the node with that child by making the parent point to the child instead of the node. The child's whole subtree moves up one level, and the rule still holds, because everything in that subtree was already on the correct side of the parent.

Case 3: two children. The node has a left child and a right child. Find the inorder successor, which is the minimum of the right subtree. Copy its value into the node that is being deleted. Then delete the successor from the right subtree. The successor has no left child, so deleting it is case 1 or case 2.

Think of case 3 as swapping the value into the spot and then removing the duplicate that was moved. The tree shape changes only at the bottom, and the rule is kept at every step.

The animation above shows the same idea in a linked list: removing a node means changing one link so that it skips the node. A tree deletion does the same thing, except that it has to choose which link to change, and two-child nodes need the extra successor step.

Case 1 in detail: deleting 20

The node 20 is a leaf. Its parent is 30, and 20 is the left child of 30. Set the left link of 30 to None. The tree becomes:

          50
        /    \
      30      70
        \    /  \
         40  60   80

The walk is now 30, 40, 50, 60, 70, 80, and the values are still sorted.

Case 2 in detail: deleting 30

Now the tree has 30 with only one child, 40, on its right. The parent of 30 is 50, and 30 is its left child. Set the left link of 50 to point to 40 instead of 30. The node 30 is no longer reachable and is removed.

          50
        /    \
      40      70
             /  \
           60    80

Node 40 has moved up one level. Every value in its subtree (only 40 itself here) is still between the new parent and the rest of the tree.

Case 3 in detail: deleting 50

Now delete the root, 50. It has two children, so this is case 3. The right subtree starts at 70. Going left from 70 reaches 60, which has no left child. So the successor is 60.

Copy 60 into the root. The root now holds 60, and the tree has two nodes that hold 60. Then delete the original 60 from the right subtree. That node is a leaf, so it is case 1. The result is:

          60
        /    \
      40      70
                \
                 80

The old leaf 60 is gone, so the left link of 70 is None. The tree still holds 40, 60, 70 and 80, and the inorder walk gives them in order.

The recursive delete

The code below turns the three cases into one recursive function. It finds the node by the normal search, then applies the cases.

def delete(root, v):
    if root is None:
        return None
    if v < root.val:
        root.left = delete(root.left, v)
    elif v > root.val:
        root.right = delete(root.right, v)
    else:
        if root.left is None:           # cases 1 and 2: no left child
            return root.right
        if root.right is None:          # case 2: no right child
            return root.left
        s = min_node(root.right)        # case 3: find the successor
        root.val = s.val                # copy its value here
        root.right = delete(root.right, s.val)   # remove it from the right subtree
    return root
 
 
def min_node(node):
    while node.left is not None:
        node = node.left
    return node

Look at the three decisions in the else branch. When root is the node to delete:

• If there is no left child, return the right child. This works for a leaf too, because a leaf's right child is None, so the function returns None, which removes the leaf. This one line covers case 1 and the right-only part of case 2.
• If there is no right child, return the left child. This covers the left-only part of case 2.
• If there are two children, copy the successor's value and delete the successor from the right subtree.

Notice the assignments: root.left = delete(root.left, v) and root.right = delete(root.right, s.val). The recursive call returns the root of the subtree after the change. Storing it back is what makes a child replacement visible to the parent. If you forget the assignment, the change happens in a copy of the link that nobody keeps.

Tracing the call that deletes 50

Follow the calls on the seven-node tree. The top call is delete(root, 50), where root is the node 50.

1. At 50, the value equals the node, so the else branch runs. Both children exist.
2. min_node(70) walks left from 70 to 60, so s is the node 60.
3. root.val = 60. The root now holds 60, and the node that used to hold 50 is gone.
4. root.right = delete(70, 60) runs. At 70, 60 is smaller, so root.left = delete(60, 60) runs.
5. At 60, the value matches. The left child is None, so the call returns root.right, which is None.
6. Back at 70, its left link is set to None. The function returns 70.
7. Back at the root, its right link is set to node 70 (unchanged). The function returns the root, which now holds 60.

The result matches the diagram in the previous section.

Why every assignment matters

The recursive delete only works because each call hands back a node, and the caller stores it. Picture the calls as a stack of plates, as in the first lesson. When delete(50, 50) is running, it has called delete(70, 60), which has called delete(60, 60). The plates come off the stack in reverse order, and each one returns a node to the plate below it.

The deepest call, delete(60, 60), finds a leaf and returns None. The plate for 70 receives that None and stores it in its left link, so 70 now has no left child. It returns node 70. The plate for 50 receives 70 and stores it in its right link. That store is a no-op, because the right link already pointed to 70, but it keeps the code correct when the subtree's root changes. Finally, the top call returns the node that now holds 60, and the caller stores it in root.

If the store on the way back were missing, the leaf 60 would be deleted from nowhere. Node 70 would still point to the old node 60 on its left. That old node is still in the tree and still holds the value 60, so the walk would print 60 twice. This is why the rule of storing every return value is not a style choice. It is what makes the links match the walk.

A full run, step by step

Before the code, follow one short sequence of deletes on the seven-node tree by hand. Each step changes one thing, so you can see exactly what the three cases do to the shape.

Step 1 is case 1. The node 80 is the right child of 70, and it has no children. The link from 70 to 80 becomes None. Nothing else moves, so the walk loses only 80.

Step 2 is case 1 again, on the other side. The node 20 is the left child of 30, and it is a leaf. Its link is set to None. The root is still 50, and the height is still 3, because the path 50, 30, 40 is as long as before.

Step 3 is case 3. The root 50 has two children, so its successor is the smallest value in the right subtree. Going left from 70 reaches 60, which has no left child, so the successor is 60. The root's value becomes 60. Then the old node 60 is removed from the right subtree. It is a leaf, so its link from 70 becomes None. The result is this tree:

        60
      /    \
    30      70
      \
       40

The new root is 60, the left subtree holds 30 and 40, and the right subtree is 70 alone. The walk prints 30 40 60 70, which is the old walk with 50 removed.

To check the table with code, run the four steps with the functions from this lesson and print walk_text(root), root.val and the height after each one. The height stayed at 3 through the whole run. Deleting can also make a tree taller, as the cost section below explains.

Running the first program

The program below builds the seven-node tree, runs the successor on several values, then deletes 20, 30 and 50, printing the inorder walk after each deletion. Each line of output tells you something specific, so compare each one with the traces above.

Its output is:

50
70
True
50
30 40 50 60 70 80
40 50 60 70 80
40 60 70 80
60

The first four lines are successor answers. 40 has successor 50, and 60 has successor 70. The successor of 80 is None, which the program prints as True when the test is is None. The successor of 45 is 50, which shows that the search works for values that are not in the tree.

Deleting 20 (a leaf) removes it cleanly. Deleting 30 (one child, 40) leaves 40 in place of 30. Deleting 50 (two children) gives the root the value 60. The last line confirms that the root is now 60.

Running the program with a list of operations

The next program reads a tree and a list of operations. Each operation is either d x (delete x and print the tree) or s x (print the successor of x). This is closer to how real data works, because you do not know the operations in advance.

The input has four parts: the count n of values, the values, the count q of operations, and then the operations, one per line. Type this exactly:

7
50 30 70 20 40 60 80
5
s 45
d 20
d 50
s 80
d 99

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
 
def insert(root, v):
    if root is None:
        return TreeNode(v)
    if v < root.val:
        root.left = insert(root.left, v)
    elif v > root.val:
        root.right = insert(root.right, v)
    return root
 
 
def successor(root, v):
    succ = None
    cur = root
    while cur is not None:
        if v < cur.val:
            succ = cur
            cur = cur.left
        else:
            cur = cur.right
    return succ
 
 
def min_node(node):
    while node.left is not None:
        node = node.left
    return node
 
 
def delete(root, v):
    if root is None:
        return None
    if v < root.val:
        root.left = delete(root.left, v)
    elif v > root.val:
        root.right = delete(root.right, v)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        s = min_node(root.right)
        root.val = s.val
        root.right = delete(root.right, s.val)
    return root
 
 
def inorder(node, out):
    if node is None:
        return
    inorder(node.left, out)
    out.append(node.val)
    inorder(node.right, out)
 
 
def walk_text(root):
    out = []
    inorder(root, out)
    return " ".join(str(v) for v in out)
 
 
n = int(input())
values = input().split()
root = None
for text in values[:n]:
    root = insert(root, int(text))
 
q = int(input())
for _ in range(q):
    op, text = input().split()
    x = int(text)
    if op == "d":
        root = delete(root, x)
        print(f"deleted {x}: {walk_text(root)}")
    else:
        s = successor(root, x)
        print(f"successor of {x}: " + ("none" if s is None else str(s.val)))

The output is:

successor of 45: 50
deleted 20: 30 40 50 60 70 80
deleted 50: 30 40 60 70 80
successor of 80: none
deleted 99: 30 40 60 70 80

Look at the last line. Deleting 99 changed nothing, because 99 is not in the tree. The search walked from the root to the None link on the right of 80 and returned None, so delete returned the tree unchanged. A delete of a missing value is harmless, and the program shows that by printing the same list again.

The line "none" if s is None else str(s.val) is a conditional expression. It checks for None before it reads s.val. Without the check, the program would crash on the successor of 80. The common mistakes section shows the exact crash.

The input().split() on the operation line gives two strings, such as ["s", "45"]. The line op, text = input().split() unpacks them into two names in one step. Unpacking needs exactly as many names as there are parts, or Python raises an error.

Two more runs

The next two programs reuse the same tree code, so you can focus on what each one asks of it. The first stores a list of values and then prints the predecessor and the successor of every stored value. It checks both walks side by side. The code is the same as the run above, with predecessor added:

def predecessor(root, v):
    best = None
    cur = root
    while cur is not None:
        if v > cur.val:
            best = cur
            cur = cur.right
        else:
            cur = cur.left
    return best
 
 
n = int(input())
values = input().split()[:n]
root = None
for text in values:
    root = insert(root, int(text))
 
for text in values:
    v = int(text)
    p = predecessor(root, v)
    s = successor(root, v)
    left = "none" if p is None else str(p.val)
    right = "none" if s is None else str(s.val)
    print(f"{v}: predecessor {left}, successor {right}")

Type 5 on the first line and 50 30 70 20 40 on the second. The output is:

50: predecessor 40, successor 70
30: predecessor 20, successor 40
70: predecessor 50, successor none
20: predecessor none, successor 30
40: predecessor 30, successor 50

Read the line for 70. Its predecessor is 50, the largest stored value below 70. Its successor is none, because nothing stored is above 70. The line for 20 is the mirror image: no predecessor, and successor 30.

The second program applies a list of deletes and prints the walk after each one. Type 5 and 50 30 70 20 40 as before, then 3 and 20 50 99. The output is:

after deleting 20: 30 40 50 70
after deleting 50: 30 40 70
after deleting 99: 30 40 70

The delete of 20 is case 1, a leaf. The delete of 50 is case 3. Its right subtree holds only 70, so the successor is 70. The root takes the value 70, and the old 70 is removed from the right side, which leaves 70 at the root with 30 on its left. The delete of 99 changes nothing, so the walk is the same as before.

What a delete costs, and what it does to the shape

Like search and insert, delete walks one path from the root down, and the recursion returns back up that path to store each new link. Each level of the walk does a constant amount of work, so the cost is O(h). The case 3 step adds two more walks down the right side of the node, one to find the successor and one to remove it. Each one costs O(h). The total is still O(h), not O(h squared), because each walk goes down one path and the walks add up to a fixed multiple of h. The extra memory is the call stack, which holds one frame per level, so it is O(h) too.

Delete changes the shape in a way that matters. Insert 50, 30, 70, 80 and 90 in that order. The root 50 has a left leaf 30, and a right chain 70, 80, 90. Now delete 30. The tree has four values left, and they form a chain of height 4: 50, then 70, then 80, then 90. A balanced tree of those same four values could have height 3, so the delete left the tree leaning, even though it did not make the tree taller. Deletes do not keep a tree balanced by themselves. A long run of random deletes usually stays fairly balanced, but a pattern of deletes can make it lean. Lesson 4 of this module is the fix for that problem.

Parent links, and why this course skips them

Some real implementations give each node a third link, to its parent. With a parent link, the successor can be found by walking up instead of down from the root, and a delete can fix its parent without a search. That design costs more memory, and every change to a link has to update the parent link too, which is easy to get wrong.

This course keeps the two links only. The price is that the code walks from the root, and a delete passes the whole path through recursion. The benefit is that the code is shorter and the rule stays easy to check. If you later meet a tree with parent links in a library or an interview, the three cases are the same. Only the way you reach the nodes changes.

A checklist for any delete

When you write or review a delete, go through these questions in order. Each one catches a bug that the others miss.

1. Does the function return the root of the subtree it was given, or None for an empty subtree? If it returns anything else, the caller's links are wrong.
2. When the value is smaller or larger than the node, is the recursive result stored in the matching link? Both branches need the store.
3. When the node has no left child, does the function return the right child? This covers case 1 and the right-only part of case 2.
4. When the node has no right child, does the function return the left child? This covers the left-only part of case 2.
5. When the node has two children, does the function copy the successor's value and then delete the successor from the right subtree? Missing the second step leaves a duplicate.
6. After a delete of a value that is not in the tree, does the tree stay exactly the same? It should, because the walk reaches None and returns it.
7. Does the inorder walk after the delete equal the walk before, minus the one value removed? This is the test that catches almost every other mistake.

Common mistakes

Mistake 1: dropping the result of the top-level delete. The recursive calls inside delete store their results, but the caller must store the result of the first call too. When the root is deleted and has only one child, the function returns that child. If the caller ignores it, the old root stays in place. Here is a two-node tree where the root is deleted with the result dropped:

root = None
for v in [50, 30]:
    root = insert(root, v)
delete(root, 50)
print(walk_text(root), "root", root.val)

The output is:

30 50 root 50

The walk still shows 50, which was supposed to be gone. The fix is root = delete(root, 50). The output with the store is 30 root 30, which is correct.

Mistake 2: copying the successor's value but not removing the successor. This is the most common wrong answer. The buggy version below copies the value and stops:

def delete_bad(root, v):
    if root is None:
        return None
    if v < root.val:
        root.left = delete_bad(root.left, v)
    elif v > root.val:
        root.right = delete_bad(root.right, v)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        root.val = min_node(root.right).val     # copied, but never removed
    return root

Run it on the seven-node tree and delete 50. The output is:

20 30 40 60 60 70 80

The value 60 now appears twice. The walk is still sorted, but the tree holds a duplicate, and the rule that every value is unique is broken. The fix is the extra line root.right = delete(root.right, s.val).

Mistake 3: reading an attribute of a successor that does not exist. If you call the successor of the largest value and read an attribute of the result, Python stops with this message:

AttributeError: 'NoneType' object has no attribute 'val'

The message says that the value None has no attribute val. The traceback above it shows the line in your file that tried to read val. The fix is to check the result first, the way the program above does with s is None.

Mistake 4: using the predecessor in one place and the successor in another. Both work, but mixing them inside one function is a sign of confusion. A bug that comes from this shows up only on some deletes, because the two methods pick different values when a node has a left subtree and a right subtree. Pick one and say which one in a comment.

Mistake 5: searching for the successor on the wrong side. The successor lives in the right subtree of the node being deleted, not in the left subtree. Searching the left side for the minimum gives the wrong value, because the left side contains smaller numbers. A quick test is to ask whether the answer is larger than the node. If it is not, you have looked on the wrong side.

Debugging walkthrough

Here is a method for any delete bug. It takes about five minutes and works on any BST.

1. Write down the inorder walk before the delete. For the seven-node tree that is 20 30 40 50 60 70 80.
2. Write down what the inorder walk should be after the delete. Remove the deleted value from the list. Deleting 50 should give 20 30 40 60 70 80.
3. Run the program and compare the two lines. If the walk has a duplicate, the successor was copied but not removed (mistake 2). If a deleted value is still there, the result was not stored back (mistake 1). If the walk is out of order, a comparison has the wrong direction.
4. Check the root. If the root is wrong after deleting the root, the case 3 copy is the likely cause. Print root.val before and after.
5. Draw the tree before and after. Two drawings, side by side, show where the links changed. Most bugs are visible on paper in one minute.

When you apply this to the buggy delete from mistake 2, step 3 already shows the duplicate 60. You do not need to trace the recursion to find the line that causes it.

A helper that prints three things after each change makes this method much faster. The walk_text helper prints the walk, and a line that adds root.val and the height shows whether the order, the root and the shape are still what you expected. Keep such a helper in your test code and remove it from the final program. It costs one line per operation and saves a long search when a bug hides in the shape rather than in the values.

Variations and edge cases

• Deleting from an empty tree. The first check returns None. Nothing breaks, and the caller must handle a None root afterwards.
• Deleting the only node. The root is a leaf, so case 1 returns None. The tree becomes empty.
• Deleting the largest value. It has no right subtree, so it falls into case 1 or case 2. It has no successor, which matters only if your code asks for one.
• Deleting a value with only a left child. Case 2 returns the left child. Check this case separately in your tests, because the right-child example is more common in tutorials.
• Deleting the same value twice. The second delete finds nothing and does nothing. Decide whether your program should report that.
• Predecessor delete. You can delete by copying the largest value from the left subtree instead. The code mirrors the one above, with max_node(root.left) in place of min_node(root.right) and the cases swapped to match.

Real-world and interview uses

Interviewers ask for BST deletion because it tests whether you can keep an invariant while changing a structure. An invariant is a rule that must always be true, here the BST rule. A good answer names the three cases, explains why the successor keeps the rule, and states the cost: O(h) time, plus O(h) stack space for the recursion. In a balanced tree that is O(log n) time. In a chain it is O(n).

Real databases and sorted containers do the same work. When a sorted set removes a key, it finds the key, handles the children, and keeps the order. Balanced-tree containers in libraries handle delete this way, so that every operation stays fast even after many deletes.

The successor idea also appears outside deletion. A scheduler might ask for the next event after a time. A calendar might ask for the next booking after a date. In both cases you use the walk from the root that keeps a candidate, which is the same code as the successor function above.

In an interview, a short answer for deletion covers four things in order. First, find the node in O(h) time. Second, name the three cases and say what each one does to the links. Third, explain that the successor is the smallest value in the right subtree, so copying it keeps the rule. Fourth, state the cost, O(h) time and O(h) stack space, and add that a skewed tree makes h equal to n. Saying the case 3 reason out loud is what separates a memorised answer from an understood one.

Practice

1. Delete 70 from the original seven-node tree by hand. Hint: 70 has two children, so the successor is the minimum of its right subtree, which is 80.

2. Find the successor of 35 in the seven-node tree without writing code. Hint: the walk turns left at 50 and at 40, and 40 has no left child, so the last candidate is 40.

3. Write predecessor(root, v) that returns the largest value smaller than v, or None. Hint: mirror the successor code, and turn right instead of left.

def predecessor(root, v):
    best = None
    cur = root
    while cur is not None:
        if v > cur.val:
            best = cur
            cur = cur.right
        else:
            cur = cur.left
    return best

4. Write max_node(node) that returns the node with the largest value. Hint: the same loop as min_node, but follow right.

def max_node(node):
    while node.right is not None:
        node = node.right
    return node

5. Write kth_smallest(root, k) using an inorder walk that stops once it has visited k nodes. Hint: keep a counter in a one-element list, and store the answer when the counter reaches k.

def kth_smallest(root, k):
    state = [0, -1]     # state[0] = values seen so far, state[1] = answer
    walk(root, k, state)
    return state[1]
 
 
def walk(n, k, state):
    if n is None or state[0] >= k:
        return
    walk(n.left, k, state)
    state[0] += 1
    if state[0] == k:
        state[1] = n.val
        return
    walk(n.right, k, state)

6. Predict the inorder walk after you insert 10, 5, 15, 12, 20 and then delete 15. Hint: 15 has two children, 12 and 20.

7. Explain why the successor of a node with two children is never above the node. Hint: it is the smallest value in the right subtree, and the right subtree is below the node.

8. Write a function count_leaves(root) that counts the leaves of a BST. Hint: a leaf has no children, so return 1 for it and the sum of the children's counts for every other node.

def count_leaves(root):
    if root is None:
        return 0
    if root.left is None and root.right is None:
        return 1
    return count_leaves(root.left) + count_leaves(root.right)

9. Write delete_iterative(root, v) without recursion, using a loop and a parent variable. Hint: handle the root as a special case, then do the three cases with the parent's link.

def delete_iterative(root, v):
    parent = None
    cur = root
    while cur is not None and cur.val != v:
        parent = cur
        cur = cur.left if v < cur.val else cur.right
    if cur is None:
        return root                         # not found: nothing changes
    if cur.left is not None and cur.right is not None:
        s_parent = cur                      # two children: move the successor up
        s = cur.right
        while s.left is not None:
            s_parent = s
            s = s.left
        cur.val = s.val
        parent = s_parent                   # now remove s, which has no left child
        cur = s
    child = cur.left if cur.left is not None else cur.right
    if parent is None:
        return child                        # the root was deleted
    if parent.left is cur:
        parent.left = child
    else:
        parent.right = child
    return root

10. Build the three-node tree with root 2 and children 1 and 3. Predict the output of the buggy delete from mistake 2 when you delete 2, then check it by running it. Hint: the buggy version copies 3 into the root and leaves the original 3 in the right subtree.

What you now know

• The inorder successor of a value is the smallest value larger than it. It is the next value in sorted order.
• You can find the successor by walking down from the root and keeping the last node where you turned left, or by taking the minimum of the right subtree.
• Deleting has three cases: a leaf is removed, a node with one child is replaced by that child, and a node with two children takes the value of its successor and then deletes the successor.
• Storing the result of each recursive call back into the parent's link is what makes the change visible.
• Check every delete with the inorder walk. It must print the same values as before, minus the one you removed, in the same order.