Leetcode Daily | 14–09–22 | Pseudo-Palindromic Paths in a Binary Tree

Hello everyone, so I am back with today’s question.

Question

Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.

Return the number of pseudo-palindromic paths going from the root node to leaf nodes.

Example:

Input: root = [2,3,1,3,1,null,1]
Output: 2 
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths only red path and green path are pseudo-palindromic paths since the red path [2,3,3] can be rearranged in [3,2,3] (palindrome) and the green path [2,1,1] can be rearranged in [1,2,1] (palindrome).

Approach

After reading the question, what comes to your mind? I thought of the question, of how I can ensure that the path is a palindrome. Now, what is a palindrome? You may know it by the syntax that has the same characters before and after the middle word. For example, imagine the word “abcba”. In this, we can read the word from front and back and it would be the same. That’s what a palindrome is. Now, the pseudo-palindrome means that any arrangement of the characters should make a palindrome.

Now for this question, we can say that if a path has 1 odd number of characters. And the total number of other characters should be even. That’s what we will look for while traversing the binary tree.

Therefore, we will count the number of odd count elements. If that exceeds more than one it means it's not a pseudo-palindrome otherwise it is a pseudo-palindrome. To count, we will use a map. Here’s the code for how you can solve this problem.

C++ Code

Python Code

Java Code

Solution

Hope you liked today’s article. Suggest me some more ways to write this kind of articles.