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++;         }     } }

Check if the given list is palindrome

You are given with the singly linked list of say having characters, you have to tell whether the list is palindrome or not.

The list is palindrome when if you iterate the list from both the ends it should generate the same string. This problem can be solved in multiple ways. Some of the approaches are discussed here.


Approach 1: Brute force

• Generate the string out of the list. 
• Now check if the list is palindrome, by simple traversing the string from both the ends and comparing each character during traversal.

This approach has many shortcomings such as space required and multiple traversals for palindrome confirmation.

 

Approach 2: Reverse the list from middle

• Find out the mid element of the list by using two pointer ( slow will increment once, fast will increment twice).
• From the middle to the end reverse the list. 
• Now use two pointers one pointing to the start of the list and other pointing to middle of the list. 
• Then iterate list till middle ( from start) comparing each element from middle till end.

In this approach we have overhead of reversing the list. If we are not allowed to modify the list then we will have to revert back the modification done.

 

Approach 3: Use recursion

• Use the reference pointer variable.
• Use slow and fast pointers to reach till middle of the list using recursion.
• Now once we have reached to the middle of the list, assign the middle element to the reference pointer variable.
• Now while coming back from the recursion, compare at each step the element with the reference variable value. 
• Point to the next node of reference variable and come out of recursion.

This is sort of reversing of the list but here we are not modifying the list. But this method will require the stack space for recursion equal to the half of the size of the list.
Advantage of this approach is we are using single pass for verifying if list is palindrome.

struct  Node {     char data;     Node * pNext; }; bool IsListPalindrome(Node* head, Node* current, Node* & reverse) {     if (head)     {         head = head->pNext;         if (head)             head = head->pNext;         else         {             reverse = current->pNext;             return true;         }         if (IsListPalindrome(head, current->pNext, reverse))         {             if (current->data == reverse->data)             {                 reverse = reverse->pNext;                 return true;             }         }         return false;     }     reverse = current;     return true; }