Binary Tree Order Bypass

Question

void traverse(Node* root) { queue<Node*> q; Node* temp_node= root; while(temp_node) { cout<<temp_node->value<<endl; if(temp_node->left) q.push(temp_node->left); if(temp_node->right) q.push(temp_node->right); if(!q.empty()) { temp_node = q.front(); q.pop(); } else temp_node = NULL; } } 

The above code is level traversal code. This code works fine for me, but one thing I don’t like, I explicitly initialize temp_node = NULL , or I use break. But that doesn't seem like good code to me.

Is there a neater implementation than this, or how can I make this code better?

Answer 1

 void traverse(Node* root) { queue<Node*> q; if (root) { q.push(root); } while (!q.empty()) { const Node * const temp_node = q.front(); q.pop(); cout<<temp_node->value<<"\n"; if (temp_node->left) { q.push(temp_node->left); } if (temp_node->right) { q.push(temp_node->right); } } } 

There is no longer a special case. And the recess is cleared, so it is easier to understand.

As an alternative:

 void traverse(Node* root) { queue<Node*> q; if (!root) { return; } for (q.push(root); !q.empty(); q.pop()) { const Node * const temp_node = q.front(); cout<<temp_node->value<<"\n"; if (temp_node->left) { q.push(temp_node->left); } if (temp_node->right) { q.push(temp_node->right); } } } 

Runs like a for loop. Personally, I like the extra variable. The variable name is more beautiful than "q.front ()" all the time.

Answer 2

You can try as follows:

 struct Node { char data; Node* left; Node* right; }; void LevelOrder(Node* root) { if(root == NULL) return; queue<Node*> Q; Q.push(root); while(!Q.empty()) { Node* current = Q.front(); cout<< current->data << " "; if(current->left != NULL) Q.push(current->left); if(current->right != NULL) Q.push(current->right); Q.pop(); } } 

Answer 3

One serious problem with your existing code is a crash when it is called on an empty tree ( root = NULL ).

You need to decide whether you want to have NULL pointers in the queue or not.

If this is not the case, you can only insert NULL values.

 void traverse(Node* root) { queue<Node*> q; // no tree no level order. if(root == NULL) { return; } // push the root to start with as we know it is not NULL. q.push(root); // loop till there are nodes in the queue. while(!q.empty()) { // dequeue the front node. Node *tmpNode = q.front(); q.pop(); // print it..we are sure it is not NULL. cout<<tmpNode->value<<" "; // enqueue left child if it exists. if(tmpNode->left) { q.push(tmpNode->left); } // enqueue right child if it exists. if(tmpNode->right) { q.push(tmpNode->right); } } } 

Alternatively, if you decide to have NULL in the queue, you can do:

 void traverse(Node* root) { queue<Node*> q; // push the root..even if it is NULL. q.push(root); // loop till the queue is not empty. while(!q.empty()) { // dequeue the front node. Node *tmpNode = q.front(); q.pop(); // the dequeued pointer can be NULL or can point to a node. // process the node only if it is not NULL. if(tmpNode) { cout<<tmpNode->value<<" "; q.push(tmpNode->left); q.push(tmpNode->right); } } } 

The first method is preferable, since a large tree has a large number of NULL child elements (leaf child nodes), and it makes no sense that they are queued in the queue when we simply do not process them later.

Answer 4

Try:

 void traverse(Node* root) { queue<Node*> q; q.push(root); while(!q.empty()) { Node* temp_node = q.front(); q.pop(); if (temp_node == NULL) { continue; } cout << temp_node->value << endl; q.push(temp_node->left); q.push(temp_node->right); } } 

Answer 5

I think that over code snippets they let you print bypassing the order of levels in an array format. This code can help you write down the solution as a level order.

 vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> a ; vector<int> b; if (root == NULL) return a; std::queue<TreeNode *> q; q.push(root); int nodeCount ; TreeNode* temp; while(true){ nodeCount = q.size(); if (nodeCount == 0) break; while(!nodeCount){ temp = q.front(); b.push_back(temp->val); q.pop(); if(temp->left != NULL) q.push(temp->left); if(temp->right!= NULL) q.push(temp->right); nodeCount-- ; } a.push_back(b); b.resize(0); } return a; } 

Output:

 [ [1], [2,3], [4,5] ] 

Answer 6

My Java solution using the queue data structure and BFS algorithm:

  void levelOrder(Node root) { //LinkedList is class of Queue interface Queue<Node> queue=new LinkedList<>(); queue.add(root); //Using BFS algorithm and queue used in BFS solution while(!queue.isEmpty()) { Node node=queue.poll(); System.out.print(node.data+" "); if(node.left!=null) queue.add(node.left); if(node.right!=null) queue.add(node.right); } } 

Answer 7

 #include<iostream> #include<queue> using namespace std; struct node{ int data; node *left,*right; }; // function for creating nodes of the tree dynamically... node * new_node(int item){ node *temp = new node(); temp->data = item; temp->left = NULL; temp->right = NULL; } //function to perform the level order tree traversal... void level_order(node *temp){ queue <node*> q; q.push(temp); while(q.empty() == false){ temp = q.front(); cout<<temp->data<<endl; if(temp->left != NULL ){ q.push(temp->left); } if(temp->right !=NULL){ q.push(temp->right); } q.pop(); } } int main(){ node *root = new node(); //Creating object of the structure node... root = NULL; root = new_node(4); root->left = new_node(3); root->right = new_node(2); root->left->left = new_node(1); level_order(root); return 0; }