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)