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

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