Friday, March 4, 2011

How many levels?

4th, March, 2011

Tree is one interesting data structure in computer science. I like the properties of trees and graphs.

Sometimes we receive some junk mails, containing junk information something like if you don't forward the mail to next 3 people something bad will happen... bla... bla... bla... and some more BS... (these mails usually related to God, even if-at-all God exists, he might be laughing at such mails. Recently I have seen a funny mail, I will post on fun to read).

But as an Electronics and Computer Science Engineer, it fascinates me to find how many pages would go for waste because of sense-less people.

We can represent the above mail chain as an m-ary tree. Where m is the branching factor, such as 3 in the above case.

As a simple math, if the mail chain ends at L-th level, how much space would they all occupy in mail servers (ofcourse this is apart from the space on user machines, assume each mail takes few MBs since those mails contain pictures as well)?. It would be in few Giga Bytes of space.

If all the persons at X-level changes the number 3 to 6, how the output will be affected?

Reverse (Synthesis) Question:

Given there are N leaves in a binary tree, how many levels an optimally balanced binary tree can have?

Answer: log2N + 1

In general, an m-ary tree with N leaves can have logmN + 1 levels.

No comments: