CODEWITHSUNDEEP
javaalgorithmdata-structurestreebinary-tree
Asif Iqbal
Asif Iqbal

Reputation: 4782

Efficient algorithm for finding the in-order rank of a binary tree node

Given a binary tree (not necessarily a binary search tree) and a node in that tree, What is an efficient algorithm (in Java preferably) to find the in-order rank of that node?

An O(n) algorithm is possible with a traversal (either recursive or iterative). Is there a better one? Thanks for any suggestion.

Upvotes: 1

Views: 1196

Answers (1)

Alex Salauyou
Alex Salauyou

Reputation: 14338

Imagine the worst case: each node has only one left child, so the whole tree becomes a linked list.

If given a root, to calculate rank you need to access the leaf, which in this case costs O(n). Thus O(n) in worst case is the best you can achieve without storing additional information in nodes.

Upvotes: 3

Related Questions