Height and Shape

Each operation follows one path down from the root. Search stops when it finds the value or reaches null. Add follows the search path to the null spot and attaches a leaf there. Remove follows the search path to the node, and in the two-child case continues down the right subtree to the successor. A path down the tree has at most $h$ edges, and each step does $O(1)$ work.

Number the levels from $0$ at the root. Level $k$ holds at most $2^k$ nodes, because each node has at most two children. So a tree of height $h$ holds at most

$$1+2+4+\cdots +2^h=2^{h+1}-1$$

nodes. To hold $n$ nodes we need

$$n\le 2^{h+1}-1⟹h\ge {\log }_2(n+1)-1$$

So the smallest height is about ${\log }_{2}n$. You get that height when every level except possibly the last is full. The largest height is $n-1$, when every node except the last has exactly one child and the tree is a single path.

Order A builds a perfect tree of height $2$:

                ╭────╮
                │ 44 │
                ╰──┬─╯
        ┌──────────┴──────────┐
     ╭──┴─╮                ╭──┴─╮
     │ 27 │                │ 68 │
     ╰──┬─╯                ╰──┬─╯
   ┌────┴────┐           ┌────┴────┐
╭──┴─╮    ╭──┴─╮      ╭──┴─╮    ╭──┴─╮
│ 15 │    │ 39 │      │ 52 │    │ 81 │
╰────╯    ╰────╯      ╰────╯    ╰────╯

Order B is sorted, so every value goes right and the tree is a single path of height $6$:

╭────╮
│ 15 │
╰──┬─╯
   └───┐
    ╭──┴─╮
    │ 27 │
    ╰──┬─╯
       └───┐
        ╭──┴─╮
        │ 39 │
        ╰──┬─╯
           └───┐
            ╭──┴─╮
            │ 44 │
            ╰──┬─╯
               └───┐
                ╭──┴─╮
                │ 52 │
                ╰──┬─╯
                   └───┐
                    ╭──┴─╮
                    │ 68 │
                    ╰──┬─╯
                       └───┐
                        ╭──┴─╮
                        │ 81 │
                        ╰────╯

Sorted input builds a degenerate tree with height $n-1$, so search, add, and remove become $O(n)$.