Thursday, September 09, 2010

Finding the highest array position needed for linear representation of a Binary Tree

If a binary tree has suppose 9 nodes then array position for storing its highest possible Root is found like this:

9 = 2^3 + 1

So it’s possible maximum Root is 2^3 – 1 = 7.

So it will take 7 x 2 = 14 places to linearly represent that tree.
And if we are to store even the possible NULLs then it takes 14 x 2 + 1 = 29 Places to linearly represent that tree.
It actually corresponds to the 2^d + 1 formula.
See, if 9 is the maximum node then the tree’s depth is actually 4. And the highest node or Root possible at that level is simply 2^d-1.

No comments:

Post a Comment

Post your comment here. If you want to say something about programming problems, scripts, software etc, please try to be as descriptive as possible.

Connect Rapoo MT750S with Linux (Tested on Manjaro)

 I bought this obvious copy of MX Master 2S in hopes of having the device switching functionality along with a lightweight body because I ha...