4 replaced http://stackoverflow.com/ with https://stackoverflow.com/

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 treestackoverflow 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?

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?

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?

3 reworded the conflict, made links more descriptive, changed title, improved formatting and sentence structure.

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

I am confused, accordingAccording to some sources such as thissources, the time complexity of calling afinding the successor functionof a node in a tree is O(h)$$O(h)$$. So, if it was a well balancedthe tree it is well balanced, the height O(logn)$$h=\log n$$, and the successor function takes time $$O(\log n)$$. ThenYet, according to this thisstackoverflow post on the time complexity of an inorder traversal of a binary search tree post, the person says, if you call n times the successor functionsfunction $$n$$ times, the time complexity is O(n)$$O(n)$$.

The statement that confuses me is What resolves the apparent contradiction between:

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

OR AND

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

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

# what is the time complexity of calling successor n times?

I am confused, according to some sources such as this, the time complexity of calling a successor function is O(h). So, if it was a well balanced tree it is O(logn). Then according to this post, the person says, if you call n times the successor functions, the time complexity is O(n).

The statement that confuses me is

if I call sucessor() function once is O(h) , that could be O(n) or O(logn) ,depending on the kind of tree

OR

The statement that I call successor() n times is O(n) in a balanced tree.

# 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?

2 formatting

I am confused, according to some sources such as http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/binarySearchTree.htmthis

, the time complexity of calling a successor function is O(h)O(h). So, so if it was a well balanced tree it is O(logn)O(logn). Then Then according to this http://stackoverflow.com/questions/12447499/time-complexity-of-bst-inorder-traversal-if-implemented-this-way

post, the person says, if you call n times the successor functions, the time complexity is O(n)O(n).

The statement that confuses me is

if I call sucessor() function once is O(h) , that could be O(n) or O(logn) ,depending on the kind of tree

if I call sucessor() function once is O(h) , that could be O(n) or O(logn) ,depending on the kind of tree

OR

The statement that I call successor () n times is O(n) in a balanced tree.

The statement that I call successor() n times is O(n) in a balanced tree.

I am confused, according to some sources such as http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/binarySearchTree.htm

the time complexity of calling a successor function is O(h), so if it was a well balanced tree it is O(logn). Then according to this http://stackoverflow.com/questions/12447499/time-complexity-of-bst-inorder-traversal-if-implemented-this-way

post, the person says if you call n times the successor functions, the time complexity is O(n).

The statement that confuses me is

if I call sucessor() function once is O(h) , that could be O(n) or O(logn) ,depending on the kind of tree

OR

The statement that I call successor () n times is O(n) in a balanced tree.

I am confused, according to some sources such as this, the time complexity of calling a successor function is O(h). So, if it was a well balanced tree it is O(logn). Then according to this post, the person says, if you call n times the successor functions, the time complexity is O(n).

The statement that confuses me is

if I call sucessor() function once is O(h) , that could be O(n) or O(logn) ,depending on the kind of tree

OR

The statement that I call successor() n times is O(n) in a balanced tree.

1