Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
4 replaced http://stackoverflow.com/ with https://stackoverflow.com/
source | link

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?

    Tweeted twitter.com/#!/StackCompSci/status/263535444430573568
3 reworded the conflict, made links more descriptive, changed title, improved formatting and sentence structure.
source | link

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
source | link

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
source | link