CODEWITHSUNDEEP
cbinary-search-tree
AdamButler
AdamButler

Reputation: 3

Print the count of even values at odd levels from a Binary Search Tree

I have a binary search tree and I need to print the total count of even values that are at odd levels.

I have an algorithm to do the traversal in order, but I don't know how to make it count the level of the tree to know if a given even value is at an odd level.

Inorder algorithm

void printInOrder(Node *root)
{
    if (root != NULL)
    {
        printInOrder(root->left);
        printf("%d ", root->key);
        printInOrder(root->right);
    }

(the level count starts at zero where the root is)
Example 1:

BST

number of even keys that are at odd levels: 2

Example 2:

BST 2

number of even keys that are at odd levels: 6

I'm really lost, any help is welcome.

Upvotes: 0

Views: 707

Answers (2)

Richa Bhuwania
Richa Bhuwania

Reputation: 180

To print the total count of even values that are at odd levels, you need to keep a global variable, that will store the count of even nodes. You need to traverse the tree inOrder wise, and only traverse over the given level for odd nodes. I am attaching the code snippet below. Print the variable c to get the required result.

int c=0; // Maintain a global variable to keep count
int printLevelOrder()
{
   int h = height(root);
  
   for(int i=1;i<=h;i++)   // i=1 -> level 0
   {
      if( (i-1)%2 != 0)   // level start from 0 and height from 1. traverse only for odd levels 
      {
          evenNode(root, i);
      }
    }
    
}

// fn to calculate the height of BST
int height(Node root)
{
    if(root == null)
      return 1;
     else
     {
         int lheight = height(root.left);
         int rheight = height(root.right);

          if(lheight > rheight)
             return lheight;
          else
             return rheight;

      }
}

// traversing at a given level
void evenNode(Node root, int level)
{
   if(root == null)
     return ;
   if(level ==1)
   {
      if(root.data %2 == 0)  // check if bode is even then increase counter.
           c++;
   }
   else if(level > 1)
   {
      evenNode(root.left , level -1);
      evenNode(root.right, level - 1);
   }
}

Upvotes: 1

dspr
dspr

Reputation: 2423

You could do something like this :

void printInOrder(Node *root, int level)
{
    if (root != NULL)
    {
        if (level & 1) {
            // Do something at odd level only
        }
        printInOrder(root->left, level+1);
        printInOrder(root->right, level+1);
    }
}

Upvotes: 0

Related Questions