CODEWITHSUNDEEP
algorithmbinary-treebinary-search-tree
Birdman
Birdman

Reputation: 1524

Minimum number of levels in BST given the number of nodes

I'm trying to find the minimum number of levels that my BST could have. I already have a function Count() that will give me the total number of nodes that exist in my tree. Just assume for this example that n = the result from Count(). So n is the number of nodes in the tree.

Here's what I'm trying right now, changed log to base 2: 

(int)Math.Log(n + 1, 2)

This seems to work only when the level is full. For example, with FULL tree with 15 nodes, it correctly displays 4 levels. Also, assume that a BST with 1 single node has 1 level (I heard sometimes people consider this 0 levels?). But if enter 13 nodes, where the BST still needs 4 levels for sure, but the level is not full, my result is inaccurate.

Is my formula wrong? Or what's my issue?

Upvotes: 0

Views: 668

Answers (1)

Birdman
Birdman

Reputation: 1524

Ok, so I think with yaman's help I have found the answer:

Math.Ceiling(Math.Log(n + 1, 2))

I tested every node from 1-20. Seems to be functioning correctly.

EDIT:

using System;

namespace Testing
{
    class TestLevelCalculation
    {
        static void Main(string[] args)
        {
            for (int n = 0; n < 34; n++)
            {
                Console.Write("Number of Nodes: " + n + " Number of Levels: ");
                Console.WriteLine(Math.Ceiling(Math.Log(n + 1, 2)));
            }
        }
    }
}

Ran this quick test code to just test with nodes 0 - 34. Seems to work properly for all node counts tested.

Upvotes: 0

Related Questions