Why is add in unbalanced Binary Search Tree O(n)?

Question

This is the implementation of add in Binary Search Tree from BST Add

private IntTreeNode add(IntTreeNode root, int value) {
        if (root == null) {
            root = new IntTreeNode(value);
        } else if (value <= root.data) {
            root.left = add(root.left, value);
        } else {
            root.right = add(root.right, value);
        }

        return root;
    }

I understand why this runs in O(log n). Here's how I analyze it. We have a tree size of n. How many cuts of 2, or half cut, will reduce this tree down to a size of 1. So we have the expression n(1/2)^x = 1 where the 1/2 represents each half cut. Solving this for x, we have log2(x) so the logn comes from search.
Here is a lecture slide from Heap that discusses runtime for an unbalanced binary search. enter image description here

My question is even if the binary search tree is unbalanced, wouldn't the same strategy work for analyzing the runtime of add? How many cuts you have to make. Wouldn't the runtime still be O(log n), not O(n)? If so, can someone show the math of why it would be O(n)?

I get that, you have to iterate over the rest of them but doesn't my way of analyzing it still work to show that its O(log n)? — committedandroider, Feb 27 '15 at 18:46
I don't understand your analysis. What is a _cut of 2_ or _half cut_? What do you mean by _reduce this tree down to a size of 1_? What does the tree look like when you add the elements above? — Sotirios Delimanolis, Feb 27 '15 at 18:47
Each time you go down the tree, you reduce the tree in "half" because you cut off the one side and you keep going it until you arrive at a tree of size 1. — committedandroider, Feb 27 '15 at 18:48
@committedandroider Nope, not always. Think about the situation when one subtree is always empty. It just decreases the size by one in this case, not halves it. — kraskevich, Feb 27 '15 at 18:49
oh, you're just cutting one off each time, making it O(n) because its going to take n cuts to get to that subtree of size 1. Thanks guys, that makes sense. — committedandroider, Feb 27 '15 at 18:50
You cut off one _side_ of the tree, but the side you cut of does not necessarily contain _half_ of the nodes. If it contains nothing, the number of remaining nodes is reduced by 1 (the node you were standing at) rather than being halved. — Aasmund Eldhuset, Feb 27 '15 at 18:50

score 4 · Accepted Answer · answered Feb 27 '15 at 18:52

With an unbalanced tree:

Your intuition of cutting the tree in half with each operation no longer applies. This unbalanced tree is the worst case of an unbalanced binary search tree. To search for 10 at the bottom of the list, you must make 10 operations, one for each element in the tree. That is why a search operation for an unbalanced binary search tree is O(n) - this unbalanced binary search tree is equivalent to a linked list. Each operation doesn't cut off half the tree -- just the one node you've already visited.

That is why specialized versions of binary search trees, such as red-black trees and AVL trees are important: they maintain trees that are balanced well enough so that all operations - search, insert, delete -- are still O(log n).

score 1 · Answer 2 · answered Feb 27 '15 at 19:02

The O(n) situation in a BST happens when you have either the minimum or the maximum at the top, effectively turning your BST into a linked list. Suppose you added elements as: 1, 2, 3, 4, 5, generating your BST, which will be a linked list due to every element having only a right child. Adding 6 would have to go down right on every single node, going through all the elements, hence making the asymptotic complexity of add O(n)

Why is add in unbalanced Binary Search Tree O(n)?

2 Answers2

Linked