Search, Add, and Remove by Hand
Every question in this section starts from this binary search tree. The tree stores no duplicate values. A node with two children is removed by copying its in-order successor’s value into it and then removing the successor.
╭────╮
│ 48 │
╰──┬─╯
┌──────────────┴──────────────┐
╭──┴─╮ ╭──┴─╮
│ 24 │ │ 72 │
╰──┬─╯ ╰──┬─╯
┌───────┴───────┐ ┌───────┴───────┐
╭──┴─╮ ╭──┴─╮ ╭──┴─╮ ╭──┴─╮
│ 12 │ │ 36 │ │ 60 │ │ 84 │
╰────╯ ╰──┬─╯ ╰──┬─╯ ╰──┬─╯
┌───┘ └───┐ └───┐
╭──┴─╮ ╭──┴─╮ ╭──┴─╮
│ 30 │ │ 66 │ │ 90 │
╰────╯ ╰────╯ ╰────╯
Solution
The search for 66 compares against 48, 72, 60, 66 and finds it. The search for 40 compares against 48, 24, 36. It then goes right from 36, reaches null, and reports that 40 is not in the tree.
Solution
The minimum is 12 and the maximum is 90. The successor of 48 is 60, the minimum of the right subtree rooted at 72. The successor of 24 is 30, the minimum of the right subtree rooted at 36.
Solution
54 becomes the left child of 60, and 40 becomes the right child of 36:
╭────╮
│ 48 │
╰──┬─╯
┌────────────────────┴────────────────────┐
╭──┴─╮ ╭──┴─╮
│ 24 │ │ 72 │
╰──┬─╯ ╰──┬─╯
┌────────┴────────┐ ┌────────┴────────┐
╭──┴─╮ ╭──┴─╮ ╭──┴─╮ ╭──┴─╮
│ 12 │ │ 36 │ │ 60 │ │ 84 │
╰────╯ ╰──┬─╯ ╰──┬─╯ ╰──┬─╯
┌────┴────┐ ┌────┴────┐ └───┐
╭──┴─╮ ╭──┴─╮ ╭──┴─╮ ╭──┴─╮ ╭──┴─╮
│ 30 │ │ 40 │ │ 54 │ │ 66 │ │ 90 │
╰────╯ ╰────╯ ╰────╯ ╰────╯ ╰────╯
Solution
12 is a leaf, so 24.left becomes null:
╭────╮
│ 48 │
╰──┬─╯
┌────────────┴────────────┐
╭──┴─╮ ╭──┴─╮
│ 24 │ │ 72 │
╰──┬─╯ ╰──┬─╯
└───┐ ┌───────┴───────┐
╭──┴─╮ ╭──┴─╮ ╭──┴─╮
│ 36 │ │ 60 │ │ 84 │
╰──┬─╯ ╰──┬─╯ ╰──┬─╯
┌───┘ └───┐ └───┐
╭──┴─╮ ╭──┴─╮ ╭──┴─╮
│ 30 │ │ 66 │ │ 90 │
╰────╯ ╰────╯ ╰────╯
36 has one child, 30, so 30 takes its place as the right child of 24:
╭────╮
│ 48 │
╰──┬─╯
┌────────────┴────────────┐
╭──┴─╮ ╭──┴─╮
│ 24 │ │ 72 │
╰──┬─╯ ╰──┬─╯
└───┐ ┌───────┴───────┐
╭──┴─╮ ╭──┴─╮ ╭──┴─╮
│ 30 │ │ 60 │ │ 84 │
╰────╯ ╰──┬─╯ ╰──┬─╯
└───┐ └───┐
╭──┴─╮ ╭──┴─╮
│ 66 │ │ 90 │
╰────╯ ╰────╯
48 has two children. Its successor is 60. Copy 60 into the root, then remove the old 60 from the right subtree. The old 60 has one child, 66, which takes its place as the left child of 72:
╭────╮
│ 60 │
╰──┬─╯
┌───────────┴───────────┐
╭──┴─╮ ╭──┴─╮
│ 24 │ │ 72 │
╰──┬─╯ ╰──┬─╯
└───┐ ┌─────┴─────┐
╭──┴─╮ ╭──┴─╮ ╭──┴─╮
│ 30 │ │ 66 │ │ 84 │
╰────╯ ╰────╯ ╰──┬─╯
└───┐
╭──┴─╮
│ 90 │
╰────╯