What is the time complexity of calling successor $n$ times during tree traversal?

According to some sources, the time complexity of finding the successor of a node in a tree is $O(h)$. So, if the tree is well balanced, the height $h=\log n$, and the successor function takes time $O(\log n)$. Yet, according to this stackoverflow post on the time complexity of an inorder traversal of a binary search tree, if you call the successor function $n$ times, the time complexity is $O(n)$.

What resolves the apparent contradiction between:

If I call the sucessor function once, the time complexity is $O(h)$, which could be $O(n)$ or $O(\log n)$, depending on the kind of tree.

AND

If I call the successor $n$ times, the time complexity is $O(n)$ in a balanced tree.

Shouldn't tree traversal take $O(n^2)$ or $O(n\log n)$ time?

-
It completely depends on how successor is implemented. What about the stack overflow post don't you understand? –  Joe Oct 30 '12 at 7:13
It may also depend on how trees are represented. Also, mind that you don't need any successor function for a traversal; maybe they guy on SO was just wrong, mixing results that should not have been mixed. –  Raphael Oct 30 '12 at 14:53
A nice compromise, if you want worst-case constant time calls to successor: just store the data at the leaves of the tree, and link together the leaves in a linked list. Then you still get $O(\log n)$ binary search, and $O(1)$ worst case successor. It doubles the space required, however. –  Joe Oct 30 '12 at 20:41

Gist: The time complexity of calling the sucessor function multiple times is not merely the product of the number of calls and the worst-case bound, though that product does encompass the worst case. Rather, if the function going to be called from every node, a more sophisticated analysis can establish a tighter worst-case bound for specific trees and implementations of the successor function.

At best, tree traversal takes at $O(n)$ time: $n-1$ calls are made to the successor function, which takes constant time. One simple example of this is the traversal of a linked list, which has a successor function that immediately returns a pointer to the next node with no additional computation.

The worst "reasonable" tree traversal would take $O(n^2)$ time: $n-1$ calls are made to the successor function, which searches all $n$ nodes before determining the successor. For example, if we have an unsorted tree and the successor is defined to be the next largest element (rather than based on its position in the tree). Of course, we could sort the tree first in time $O(n\log n)$ and in general, if we expect to call the successor function $n$ times, it would be wise to preprocess the tree so that it can be traversed in one of the three canonical ways: inorder, preorder, or postorder.

Ok, time to clear a misconception! Let's ask what's the best-case and worst-case scenarios for the successor function are when we have an inorder traversal of a binary search tree:

Remember that in inorder traversal, the left subtree is visited, then the parent node, then the right subtree. So an inorder traversal in the tree above gives us $[A,B,C,D,E,F,G,H]$. (For contrast, preorder traversal would have given us $[F,B,A,D,C,E,G,I,H]$). We start at the beginning of the tree at $A$. From $A$, the successor function checks to see that it has no right subtree (it doesn't) before finding its closest ancestor for which it is the descendant of the left child. But wait! I didn't tell you that each node had knowledge of its ancestors, so we potentially have to search the entire tree just to determine where $A$ is! So now we split into two cases:

• Worst-case: Assuming that our node has no right subtree, if the tree was a binary search tree, we could find the node in $O(\log n)$ time. But worst-case, it's not a binary search tree; in fact, it has no structure, so every call takes $O(n)$ time, but if we're consistent about how we search, the total number of steps to find the node's successor is at least $\sum_{x=1}^{n}x=\frac{(n)(n+1)}{2}=O(n^2)$.

• Best-case: Each node has a link to its ancestor, so from $A$ to $B$ takes two steps (check for right subtree; back up to ancestor for which it is the left child). The successor function that takes the most steps is from $E$ to $F$, for which $E$ first checks that it has no right subtree, then checks to see if it is the left child of $D$ (it isn't), or the descendent of the left child of $B$ (it isn't), and finally if it is the descendent of the left child of $F$ (it is). That took $O(h)=O(\log n)$ steps, but most calls to the function won't take that many steps. Quoting the SO post, "observe that each edge in the tree gets visited at most twice (once from parent to child and once from child to the parent)" so the total number of nodes visited is $2n$ and hence $O(n)$ worst-case bound.

Another way to appreciate that the average call to successor is $<\log(n)$ is to consider a balanced tree with $n$ nodes and roughly $n/2$ leaves. Half of all successor function calls will be to an ancestor, half of which are from the left child ($\frac{1}{4}n$) and thus takes only one generation/step, $\frac{1}{8}n$ go back two generations, $\frac{1}{16}n$ go back three. Hopefully you see the pattern: $\sum_{i=1}\frac{i}{2^{i+1}}$ converges to $1$. And the other half does the step-analogous $\min$ function (searching it's right subtree for the leftest child), so it also converges to $1$. The expected time is thus $2$ (if I've done my math carefully). So that's $n-1$ calls to a successor function that on average takes ~$2$ steps $\rightarrow O(n)$ time.

-
How did you know 1/4 n, are from left child? . The thing that i am confused, is what actually is time complexity, I thought time complexity, meant the number of nodes you have to visit, so if you call successor once that is O(h), so just to be clear you are saying that first call is O(h) then second call will be O(h/2), since now the nodes are less? . Do we have to go to A and E using find min and max function from node B ? before calling sucessor and predecessor. Thanks Merbs, your explanations to my post are great. –  user1675999 Oct 30 '12 at 11:41
We have (n/2) are leaves, and (1/2) of leaves are left children -> (n/4). Time complexity is relative, so it can certainly be measured in nodes you have to visit. Big $O$ notation is used as a worst-case measure, so when we say a single call is $O(h)$, we mean that at worst it will take on the magnitude of $h$ steps. Since there is additional structure to tree traversal, straight-up multiplication is valid strategy ($O(n^2)$ encompasses $O(n)$) but not the best we can do. As for your last question, it depends on the implementation, but I think so. –  Merbs Oct 30 '12 at 12:11
"Simply multiply the expected case by the number of calls to get the precise total number of steps and hence the actual time complexity." -- I think you mix notions here in an unfortunate way. It's not expected time as such (in a stochastic sense) you want to look at; rather, you want amortised analysis. –  Raphael Oct 30 '12 at 14:51
Very true; I was trying to illustrate that although any particular call to the successor function takes at worst $O(h)$, the average call takes (potentially) constant steps. As an aside for others, the idea of being able to start inorder traversing at any random node via the successor function without a stack is interesting: it doesn't seem to increase the time complexity but reduces the space complexity? Albeit, nodes have to carry additional information about their parents. –  Merbs Oct 30 '12 at 16:06
$h = O(\log n)$ assuming the tree is balanced, of course. –  Joe Oct 30 '12 at 20:39