0
$\begingroup$

If there are 16 leaves in a full binary tree and two nodes $a$ and $b$ chosen at random, then what is the expected value of the distance between $a$ and $b$ in T?


My question here is, how do I correctly approach this question?


(Also tell me how to develop numerical skill in algorithm?)

$\endgroup$
3
$\begingroup$

Let's name the nodes $\mathit{node0}$ through $\mathit{node15}$. (with the implication that that's the order of the nodes)

I would approach this problem first by saying "if $a$ is $\mathit{node0}$, then what's the expected value of the distance between $a$ and $b$?" Then I'd ask the question "what if $a$ is $\mathit{node1}$?", etc. Presumably along the way there would be patterns and symmetries I could make use of so I wouldn't need to do a long calculation 16 times.

So let's take that first question: "if $a$ is $\mathit{node0}$, then what's the expected value of the distance between $a$ and $b$?"

First off, the distance between $\mathit{node0}$ and $\mathit{node0}$ is $0$. To $\mathit{node1}$, the distance is $2$. To nodes $\mathit{node2}$ or $\mathit{node3}$, the distance is $4$. To the four nodes $\mathit{node4}$ through $\mathit{node7}$, the distance is $6$. To the remaining eight nodes the distance is $8$.

So the expected distance when $a$ is $\mathit{node0}$ is $(0 + 2 + 2*4 + 4*6 + 8*8)/16 = 6.125$.

Now figure out the expected distance when $a$ is $\mathit{node1}$, and then other nodes. (there is an obvious pattern - prove it)

Then average over those results to find the answer.

Often, you will find a shorter or more elegant solution to a problem as you are working on it. This is normal, and should not be taken as a sign that your initial approach was wrong or that you should have seen the more elegant approach without trying your initial approach first, any more than a writer should expect to write an essay without first writing some notes or a rough draft.

Unfortunately, though writers are often trained in the idea of rough drafts and revisions, solutions to math or computer science problems are usually only presented in their final form without much indication of the bumbling around and blind corners that really went into discovering the elegant explanation.

$\endgroup$
  • $\begingroup$ "To $\mathit{node1}$, the distance is $2$. To nodes $\mathit{node2}$ or $\mathit{node3}$, the distance is $4$." how?? Can u draw how node1 getting distance 2 and node2 and node3 both getting distance 4?? $\endgroup$ – Srestha Mar 14 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.