Printing Binary tree in leverl order C++

Given a binary tree, print tree in level order. Consider tree given in below image 

For above tree the level order should be printed as 

9

15  8

4  3  11

Approach 1:

Try to solve this problem in iterative manner. If we go iteratively from root to each level we can easily print the level order. But the problem here will be you should store the next level nodes on every level. This we can achieve using a queue of nodes. So while iterating any level we will add next level nodes in the temporary queue and will pull back those for next iteration. 

Function "PrintLevelOrderIterative" uses the method describe here.

void PrintLevelOrderIterative(Node * pRoot) {     if (pRoot)     {         queue<Node*> nodes;         nodes.push(pRoot);         while (!nodes.empty())         {             queue<Node*> temp;             while (!nodes.empty())             {                 Node * node = nodes.front();                 nodes.pop();                 cout << node->data << " ";                 if (node->pLeft)                     temp.push(node->pLeft);                 if (node->pRight)                     temp.push(node->pRight);             }             swap(nodes, temp);             cout << endl;         }     } }

The above approach can be modified to use single queue as well by using NULL pointer as end of each level as done in below code.

void PrintLevelOrderWithSingleQueue(Node * pRoot) {     if (pRoot)     {         queue<Node *> nodesQ;         nodesQ.push(pRoot);         nodesQ.push(NULL);         while (!nodesQ.empty())         {             Node * tmp = nodesQ.front();             nodesQ.pop();             if (tmp)             {                 cout << tmp->data << "  ";                 if (tmp->pLeft)                     nodesQ.push(tmp->pLeft);                 if (tmp->pRight)                     nodesQ.push(tmp->pRight);             }             else             {                 cout << endl;                 if (!nodesQ.empty())                     nodesQ.push(NULL);             }         }     } }

Approach 2:
The above approach will require the storage for storing the two level nodes, current level nodes as well as next level nodes. If we dont want that then we can use the recursive approach. Here first we will find out the height of the tree, so that we know at what level to stop. Then go recursive in in-order manner and print each level every time. This approach requires "n long(n)" time complexity where "n" denotes nodes in the given binary tree.

void PrintLevel(Node * root, int level, int current) {     if (root)     {         current++;         if (current < level)         {             PrintLevel(root->pLeft, level, current);             PrintLevel(root->pRight, level, current);         }         if (current == level)         {             cout << root->data << "  ";         }     } } int max(int a, int b) {     return (a > b ? a : b); } int HeightOfTree(Node * root) {     if (root)     {         return (1 + max(HeightOfTree(root->pLeft), HeightOfTree(root->pRight)));     }     return 0; } void PrintLevelOrderRecursive(Node * root) {     if (root)     {         int height = HeightOfTree(root);         int counter = 1;         while (height >= counter)         {             PrintLevel(root, counter, 0);             cout << endl;             counter++;         }     } }

Root to leaf path with specified sum in a binary tree

The problem here is "To find if there is any root to leaf path with specified sum in a binary tree."

Consider the binary tree shown in the tree below .

We have to find whether there is any path which goes from root to any leaf having sum equal to given sum.
For example if we have given sum as 28 then there can be two paths which has sum 28.
9->8->11 or 9 ->15->4.

Approach 1:

• Perform the level order traversal. 
• During  level order traversal find out all the root to leaf paths exists in the tree.
• Now for each path check if all the nodes sum equals to given sum. 

This approach will require large space to store all the paths formed during level order. Then again we will have to iterate through all the nodes for finding the sum. 

Approach 2:

• Perform the post order traversal. 
• During post order traversal maintain stack of the nodes visited and sum so far.
• If we have reached to leaf then check if sum so far is same as required sum. 
• If yes.. print the path else pop the current root and continue.

This approach does usages the temporary space but that will always be equal to maximum height of the tree. Also as every node is visited only once the time complexity will be O(n) where n being number of nodes in the tree.

 

Code below shows both ways to check if given sum exists in the any root to leaf path if exists then how to print the path.

struct Node {     int data;     Node * pLeft;     Node * pRight; }; //Just check if sum exists bool CheckIfSumExistInRTLPath(Node * pRoot, int sum, int currentSum) {     if (pRoot)     {         currentSum += pRoot->data;         bool left = CheckIfSumExistInRTLPath((pRoot->pLeft, sum, currentSum);         bool right = CheckIfSumExistInRTLPath((pRoot->pRight, sum, currentSum);         if (!(pRoot->pLeft) && !(pRoot->pRight) && currentSum == sum)         {             cout << " Found matching sum at the leaf : " << pRoot->data << endl;             return true;         }         return (left || right);     }     return false; } //Print the path if provided sum exists bool GetRTLPathForSum(Node * pRoot, int sum, int currentSum, stack<Node*> & path) {     if (pRoot)     {         currentSum += pRoot->data;         path.push(pRoot);         bool left = GetRTLPathForSum(pRoot->pLeft, sum, currentSum, path);         bool right = GetRTLPathForSum(pRoot->pRight, sum, currentSum, path);         if (!(pRoot->pLeft) && !(pRoot->pRight) && currentSum == sum)         {             cout  << endl << " Found matching sum at the leaf : " << pRoot->data << "   The PAth : " << endl;             stack<Node*> temp;             while (!path.empty())             {                 Node * node = path.top();                 temp.push(node);                 path.pop();                 cout << node->data << "  ";             }             while (!temp.empty())             {                 path.push(temp.top());                 temp.pop();             }             path.pop();             return true;         }         path.pop();         return (left || right);     }     return false; }