The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote

In a complete binary tree of n nodes, how far are the two most distant nodes ? Assume each edge in the path counts as !

  1. About $\log_{2} n$
  2. About $2 \log_{2} n$
  3. About $n \log_{2} n$
  4. About $2n$
asked in DS by Boss (29.3k points)
recategorized by | 851 views
why not 2$\log n$

1 Answer

+1 vote
If one node is present at extreme left side of the leaves and other node at the other extreme right side of the leaves ,then these two nodes have to cover up height 2 times .From extreme left to root and then from root to Extreme right .

Height of Binary tree$= \log_{2}n$

so Answer is $= \log_{2}n$ + $ \log_{2}n$ =$2 \log_{2}n$
answered by Boss (15.9k points)
Yes, although no need to be in extreme corner. just need to be at the last layer.

Yep it makes sense for complete binary tree 

@sourav,How wud the diagram for the above question will be drawn?

Distance between $H \rightarrow O$ or $I \rightarrow O$

@sourav,Thanks. :)

Devshree Dubey you are welcome!

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,587 questions
54,197 answers
71,151 users