C++ Programming - BST Level Order Printing

Q. Level Order traversal of Binary Search Tree

This will traverse the BST in levels and print the elements according to the level from left to right.

Node:

struct Node {
    Node *left;
    Node *right;
    int data;
    Node(int value) : data(value) 
    {
        left = right = NULL;
    }
};

Explaination:
This is a common solution.

The logic behind this we start of with a queue which is having the root node as the only entry in the queue. Then we starts traversing the queue till it become empty during which we will be pushing the node's left and right into the queue along with pop the first entry and printing its data value.

BinaryTree Class:



class BinaryTree {
 Node *root;

 void insert(Node **node, int data) 
 {
  if (  *node == NULL ) 
   *node = new Node(data);
  else {
   if ( data <= (*node)->data )
    insert(&((*node)->left),data);
   else
    insert(&((*node)->right),data);
  }
 }

 public:
 BinaryTree() : root(NULL) { }
 void insert(int data) 
 {
  insert(&root,data);
 }


 void levelorder() {
  std::queue levelq;

  levelq.push(root);
  while( levelq.size() > 0 ) {
   Node *cur = levelq.front();
   std::cout << cur->data << "  ";
   levelq.pop();
   if (cur->left)  levelq.push(cur->left);
   if (cur->right) levelq.push(cur->right);
  }
 }
};


Labels:

About this entry

You’re currently reading “C++ Programming - BST Level Order Printing,” an entry on ANOOB BACKER Technical Blog

Published:
7:11 am
by -