591 views

1 Answer

1 votes
1 votes

Answer: $\log_{2} (n)$

Reason:

In worst case a binary tree may go upto ( n ) levels making the height of the tree (n-1)
Otherwise a binary tree may go upto ( $\log_{2} (n)$+c ) levels making the height of the tree ( $\log_{2} (n)$+c -1 )

We can run recursive calls to find the height.

pseudocode:
 

start from root node
heightOfCurrentNode = 1 + max ( heightOfLeftNode() + heightOfRightNode() )
return heightOfCurrentNode

Hence time complexity to find the height of a binary tree is—

O(n) – in worst case
O($\log_{2} (n)$) – in best case and average case

In general if the question is what is the time complexity to find the height of a binary tree then answer would be O(n)

edited by