Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Understanding the Problem
3.
Intuition
3.1.
Code
3.2.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is a Binary Tree?
4.2.
What is Level Order Traversal?
5.
Conclusion
Last Updated: Mar 27, 2024

Palindromic Levels Of a Binary Tree

Author Saksham Gupta
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

Palindrome and Level order traversal of a binary tree are two questions that are asked frequently in coding interviews, But what happens when you combine these two concepts? We get something that we call Palindromic Levels Of a Binary Tree in which we have to print only those levels which are palindromic.

Also see, Data Structures

Understanding the Problem

We have been given a binary tree, and we have to print its level order traversal, But we only have to print those levels which are palindrome. This thing will become clear in the following example.

Binary Tree

Now, if we print the level order traversal of the tree, we will get

1
2 3
9 6 6 9

According to the question, we only have to print those levels which are palindromic. Thus our output will be

1
9 6 6 9
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Intuition

The intuition is very straightforward, We’ll do a regular level order traversal using a queue, and after we have computed a particular level, we will check if it’s a palindrome or not. If it’s a palindrome, we will print it; otherwise, we will skip it. 

Now let’s look at the code for the above algorithm.

Code

#include <iostream>
#include <queue>

using namespace std;

// Binary Tree Node Class.
template <typename T>
class BinaryTreeNode
{
public:
    T val;
    BinaryTreeNode<T> *left;
    BinaryTreeNode<T> *right;

    BinaryTreeNode(T val)
    {
        this->val = val;
        left = NULL;
        right = NULL;
    }
};

// Function to check palindrome.
bool isPalindrome(vector<int> v1)
{
    for (int i = 0, j = v1.size() - 1; i < j; i++, j--)
    {
        if (v1[i] != v1[j])
            return false;
    }
    return true;
}

void levelOrderPalindrome(BinaryTreeNode<int> *root)
{
    // Queue for level order traversal.
    queue<BinaryTreeNode<int> *> q1;
    // Base Case.
    if (root == NULL)
        return;
    q1.push(root);

    while (q1.size() != 0)
    {
        // Vector to store level order traversal of each level.
        vector<int> v1;
        int s = q1.size();
        while (s > 0)
        {
            BinaryTreeNode<int> *top = q1.front();
            v1.push_back(top->val);

            // Pushing its left and right node.
            if (top->left != NULL)
                q1.push(top->left);
            if (top->right != NULL)
                q1.push(top->right);
            s--;
            q1.pop();
        }

        // If the level is palindromic, then we will print it.
        if (isPalindrome(v1))
        {
            for (int i = 0; i < v1.size(); i++)
                cout << v1[i] << " ";
            cout << endl;
        }
    }
}

BinaryTreeNode<int> *takeInput()
{
    int rootData;
    cin >> rootData;

    if (rootData == -1)
    {
        return NULL;
    }

    BinaryTreeNode<int> *root = new BinaryTreeNode<int>(rootData);
    queue<BinaryTreeNode<int> *> q;
    q.push(root);

    while (!q.empty())
    {
        BinaryTreeNode<int> *currentNode = q.front();
        q.pop();
        int leftChild, rightChild;

        cin >> leftChild;
        if (leftChild != -1)
        {
            BinaryTreeNode<int> *leftNode = new BinaryTreeNode<int>(leftChild);
            currentNode->left = leftNode;
            q.push(leftNode);
        }

        cin >> rightChild;
        if (rightChild != -1)
        {
            BinaryTreeNode<int> *rightNode = new BinaryTreeNode<int>(rightChild);
            currentNode->right = rightNode;
            q.push(rightNode);
        }
    }
    return root;
}

int main()
{
    // Taking input.
    BinaryTreeNode<int> *root = takeInput();

    // Calling 'levelOrderPalindrome()' function.
    levelOrderPalindrome(root);
}

 

Input

1 2 3 9 6 6 9 -1 -1 -1 -1 -1 -1 -1 -1

Here we are taking input level order wise and -1 here represents a NULL node.

Binary Tree

The input tree would look something like this.

Output

1
9 6 6 9

Complexity Analysis

Time Complexity

The Time Complexity is O(N), where ‘N’ is the number of nodes in the tree. 

The level order traversal would cost O(N) time as each node is pushed exactly once in the queue. 

Let us analyze the time complexity in terms of palindrome check. As the worst case will occur when the tree is a complete binary tree. Now for the palindrome check, for the first level, it will take 2 ^ 0 times, for the second level it will take 2 ^ 1 times, for the third level it will take 2 ^ 2 time,s and so on. Thus the overall complexity would be the summation of 2 ^ 0 + 2 ^ 1 + 2 ^ 2 ……….2 ^ (log (N - 1)).

This is a GP with the first term, a = 1, and common ratio, r = 2.

Let the number of terms in this GP be k.

Then last term, 2 ^ (log(N - 1)) = a * r ^ (k - 1)

  2 ^ (log(N - 1)) = 1 * 2 ^ (k - 1)

  2 ^ (log(N - 1)) = 2 ^ (k - 1)

  log(N - 1) = (k - 1)

  k = log(N - 1) + 1

Hence, the sum of series = a * (r ^ k - 1) / (r - 1) = 1 * (2 ^ k - 1) / (2 - 1) = 2 ^ k - 1 = 2 ^ (log(N - 1) - 1 = log(N - 1) - 1

Overall time complexity = O(log(N) + O(N)) = O(N)

Space Complexity

The Space Complexity is O(N), where 'N' is the number of nodes in the tree.

Since we are using a queue for level order traversal, it will take extra O(N) space.

You can also read about Palindrome Number in Python here.

Frequently Asked Questions

What is a Binary Tree?

A Binary Tree is a type of Tree in which each node has a maximum of 2 children.

What is Level Order Traversal?

Level Order Traversal is the technique of traversing a Tree where the Nodes of a tree that have the same height are grouped together.

 

Conclusion

Now you have understood how to find the palindromic levels of a binary tree,  which refreshed your concepts about palindrome and level order traversal of a Binary Tree. 

Recommended Reading: 

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Previous article
Diamond Tree
Next article
Convert the Given binary Tree into a Symmetric Tree by adding a minimum number of nodes
Live masterclass