CODEWITHSUNDEEP
c++binary-search-treenodes
Viktor
Viktor

Reputation: 21

Counting the number of nodes in a level of a binary search tree

Like the title says, I want to count the nodes in for any given level of the tree. I already know how to make member functions for counting all the nodes of the tree, just not sure how to approach a specific level. Here's what I've tried. Any help is appreciated.

First parameter is a point to a character array inputted by the user. root is a private variable representing the "oldest" node. 

int TreeType::GetNodesAtLevel(ItemType* itemArray, int level)
{
    TreeNode* p = root;

    if (itemArray == NULL)
        return;
    if (level == 0)
    {
        cout << p->info << " ";
        return;
    }

    else
    {
        GetNodesAtLevel(itemarray->left, level); //dereference in one and not the other was just testing 
        GetNodesAtLevel(*itemarray->right, level); //neither seems to work
    }
}

Upvotes: 0

Views: 655

Answers (1)

Agrudge Amicus
Agrudge Amicus

Reputation: 1103

The way to do it is by using a queue (employing level order traversal - BFS). Now follow this:

Take two variables, count_level and count_queue (keeping total nodes in a queue).

for a tree like this:

               A 
              / \
             B   C
            / \   \
           K   L   D
                   /
                  E

initially count_level = 0 and count_queue = 0. Now:

  1. Add a node to the queue(at this point A, increment count_queue to 1).
  2. Now when you find count_level = 0 do this -> count_level = count_queue.
  3. Add the kid nodes while dequeuing till the count_level becomes 0. So at this point the follow step 2 and that will give you the no of nodes at level beneath what just has been processed.

Upvotes: 1

Related Questions