Pseudo Palindromic Paths in a Binary Tree

Problem Link: https://leetcode.com/problems/pseudo-palindromic-paths-in-a-binary-tree/

Problem Statement

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.

Note: The node values of a path form a palindrome if at most one digit has an odd frequency (parity).

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

Example 1:

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 the leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths, only the 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).

Example 2:

Input: root = [2,1,1,1,3,null,null,null,null,null,1]

Output: 1

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

Example 3:

Input: root = [9]

Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 10⁵].
1 <= Node.val <= 9

Disclaimer: Before proceeding forward towards the solution it is recommended to try first!!

Intuition

The given problem statement can be divided into two subproblems:

Traverse the tree to build root-to-leaf paths.
For every root to leaf path, check if the nodes form a pseudo palindromic path.

The problem looks a bit difficult but if we closely think, it is rather an easy problem. Let’s look at intuition diving into the problem.

As mentioned in the problem statement that a root to leaf path is a palindrome only if at most one of the node has an odd frequency (parity). We can easily check this by traversing the tree from root to leaf and keeping a track of the frequencies of nodes in the current path. As soon as we reach the bottom (leaf node) we can check the frequencies to see if only at most one of the nodes has an odd frequency. If yes, then we can say it is a palindromic path else it is not a palindromic path.

Brainstorm🤔: Can we figure out a way to compute the parity on the fly instead of capturing the frequencies?

Approach

There are two approaches to solving the problem:

Using Dictionary: The first one is simply keeping a track of frequencies on the go traversing from root to leaf and checking them at the leaf node for the palindromic path.
Using Bit Manipulation: This approach is also similar to the previous approach, the only difference is in order to minimize the space complexity we will calculate the parity on the fly using Bitwise XOR and Left Shift operation. Left shift operator will be used to define the bit and XOR to compute the digit frequency. Whenever we are on the leaf node we will check for a palindromic sequence using Bitwise AND.

Using Dictionary

In order to traverse through the given tree we will use preorder traversal.

As in the problem statement it is mentioned that the node values ranges from 0 to 9 therefore, In order to capture the frequencies we will use an array of size 9. Here, every element in the array will store the frequency of element at it’s index.
We keep on increment array[node] for every node we traverse. If we do not have a left or a right child we check within the array if there is at most one element with odd frequency. If yes, we return the answer as 1 else 0.
Finally, if the current node is not a leaf node we return the submission of results obtained from it’s left and right child.

Code

Complexity

T(n): O(n)
S(n): O(n)

Using Bit Manipulation

Again, we will use preorder traversal to traverse the tree.
Here in order to calculate the parity on the fly, we will use Left Shift to define the digit and XOR for the frequency. The idea is is to keep the frequency of digit 1 in the first bit, 2 in the second bit, etc.

Let’s understand what (1 << i) means. It means shifting ‘1’ ‘i’ bits to the left. In other words it is just 2 ^ i.

We can use (1 << i) to set the appearance of digit i and in order to count the odd frequency, we can use XOR properties. Therefore, if the i-bit is set, then digit i has an odd frequency.
- If a digit appears even number of times, the bit at the end will be 0. (x ^ x = 0)
- If a digit appears odd number of times, the bit at the will be 1. (x ^ x ^ x = (x ^ x) ^ x = 0 ^ x = x)

If i-bit is set in path variable, that means digit ‘i’ has an odd frequency. Therefore, the number of 1’s in path variable equals to the number of digits with an odd frequency. However, we only want at most one digit that has an odd frequency. To achieve this we can use the bit trick (path & (path-1)) to remove the rightmost set bit. If the result is 0, that means we have at most one digit that has an odd frequncy. Therefore, add one to ans.

Code

Complexity

T(n): O(n)
S(n): O(h)

Problem Solving

Pseudo Palindromic Paths in a Binary Tree