1

The code which I have written gives the correct output. I just wanted to know if this method will run into problems with larger input sizes.

#include <bits/stdc++.h> 
using namespace std;

//LEVEL ORDER TRAVERSAL

class node{
 private: int data;
 public : node* left=NULL;node *right=NULL;
 node(int dat){
     data=dat;
 } 
 int getVal(){
     return data;
 }
};

void level_order(node *a,queue<node*> q){
  if(a->left!=NULL){
    q.push(a->left);
  }
  if(a->right!=NULL){
    q.push(a->right);
  }
  cout<<a->getVal()<<",";
  q.pop();
  if(!q.empty()){
  level_order(q.front(),q);}
}

int main(){
    node* root=new node(1);
    root->left=new node(2);
    root->right=new node(3);
    root->left->left=new node(4);
    root->left->right=new node(5);
    root->left->right->left=new node(6);
    root->right->left=new node(7);
    root->right->right=new node(8);
    root->right->right->left=new node(9);
    root->right->right->right=new node(10);
    queue<node*> a;
    a.push(root);
    level_order(root,a);
    return 0;
}

I am just getting started with Data Structures. Sorry if this seems like a silly question.

Kshitij_Jha_7
  • 73
  • 7

1 Answers1

2

If the tree is degenerate (skewed) in the sense that it is completely unbalanced (nodes never have two children, i.e. each level has just one node), then the number of levels is O(), and thus the stack space needed for recursion is also O(). This means you could hit the stack space limit... If however you are confident the tree will have a height that is O(log), then there is no issue.

Still, as that function is tail recursive, you can easily rewrite it as an iterative procedure.

Other remarks

  • Don't use #include <bits/stdc++.h>. Instead include the standard libraries you need (iostream and queue in this case).
  • Don't use using namespace std
  • Preferrably use nullptr in C++
  • Explicitly comparing with NULL is not needed
  • Put separate statements on separate lines. So not public : node* left=NULL;node *right=NULL;
  • Put closing braces at the start of a line, so not level_order(q.front(),q);}
  • Use meaningful names. a is meaningless. q is not so bad, as it is common practice for naming a queue variable.
  • level_order passes a node that is also at the front of the queue: this is overkill: you might as well only pass the queue and let the first action be to extract that front element.

Here is a possible iterative implementation of a level order traversal:

void levelOrder(std::queue<Node*> nodes) {
    while (!nodes.empty()) {
        Node *root = nodes.front();
        nodes.pop();
        std::cout << root->getVal() << ",";
        if (root->left) {
            nodes.push(root->left);
        }
        if (root->right) {
            nodes.push(root->right);
        }
    }
}
trincot
  • 317,000
  • 35
  • 244
  • 286