# Pseudo-Palindromic Paths in a Binary Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/pseudo-palindromic-paths-in-a-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/pseudo-palindromic-paths-in-a-binary-tree
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
---
## Problem
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 1:**

![](https://assets.glich.co/dsa/pseudo-palindromic-paths-in-a-binary-tree/image0.png)

**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).

**Example 2:**

**![](https://assets.glich.co/dsa/pseudo-palindromic-paths-in-a-binary-tree/image1.png)**

**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 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, 105]`.
* `1 <= Node.val <= 9`

# Approaches
## Depth-First Search with Frequency Counting
This approach uses a standard Depth-First Search (DFS) to traverse the tree from the root to each leaf. During the traversal, it maintains a frequency count of the digits encountered along the current path. When a leaf node is reached, it checks if the path is pseudo-palindromic by analyzing these counts.
**Time:** O(N), where N is the number of nodes in the tree. We visit each node exactly once. At each leaf node, we perform a check that takes constant time (iterating 9 times), so the overall complexity is proportional to the number of nodes. · **Space:** O(H), where H is the height of the tree. The space is dominated by the recursion stack depth. In the worst case of a skewed tree, H can be equal to N (the number of nodes), leading to O(N) space. The frequency array uses constant O(1) space.
**Pros:** Conceptually straightforward and easy to understand.; Directly models the problem by counting frequencies, making the logic clear.
**Cons:** Slightly less performant than the bitmasking approach due to the overhead of iterating through the frequency array at each leaf.; Requires careful implementation of backtracking to avoid incorrect counts and to manage memory efficiently.
### Explanation
A path's node values can form a palindrome if at most one digit appears an odd number of times. We can implement a recursive DFS function, say `dfs(node, counts)`, that explores the tree. The `counts` parameter is an array that stores the frequency of each digit (1-9) from the root to the current `node`.

The main function initializes a counter for pseudo-palindromic paths to zero and an empty frequency array, then calls `dfs(root, counts)`. The key to this approach is backtracking. After visiting a node and its descendants, we must undo the change made to the frequency count for that node. This ensures that when we explore a sibling branch, the counts accurately represent the path to that sibling's parent, not the path through the previously explored cousin nodes.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int count = 0;

    public int pseudoPalindromicPaths (TreeNode root) {
        int[] pathCounts = new int[10];
        dfs(root, pathCounts);
        return count;
    }

    private void dfs(TreeNode node, int[] pathCounts) {
        if (node == null) {
            return;
        }

        // Add current node to the path
        pathCounts[node.val]++;

        // If it's a leaf node, check for pseudo-palindrome
        if (node.left == null && node.right == null) {
            if (isPseudoPalindrome(pathCounts)) {
                count++;
            }
        } else {
            // Continue traversal
            dfs(node.left, pathCounts);
            dfs(node.right, pathCounts);
        }

        // Backtrack: remove current node from the path
        pathCounts[node.val]--;
    }

    private boolean isPseudoPalindrome(int[] counts) {
        int oddCount = 0;
        for (int i = 1; i <= 9; i++) {
            if (counts[i] % 2 != 0) {
                oddCount++;
            }
        }
        return oddCount <= 1;
    }
}
```
### Algorithm
- Initialize a global or member variable `count` to 0.
- Create a frequency array `counts` of size 10, initialized to all zeros, to store the frequency of digits 1 through 9.
- Define a recursive DFS function, let's call it `dfs(node, counts)`.
- In the `dfs` function:
  - If the current `node` is null, return immediately.
  - Increment the frequency of the current node's value: `counts[node.val]++`.
  - Check if the current node is a leaf node (i.e., `node.left == null && node.right == null`).
    - If it is a leaf, check if the current path is pseudo-palindromic. This is done by a helper function that iterates through the `counts` array and counts how many digits have an odd frequency. If the number of odd-frequency digits is 0 or 1, increment the global `count`.
  - Recursively call the function for the left and right children: `dfs(node.left, counts)` and `dfs(node.right, counts)`.
  - **Backtrack:** After the recursive calls for the children return, decrement the frequency of the current node's value: `counts[node.val]--`. This step is crucial to correctly reflect the path state as the traversal unwinds.
- Start the traversal by calling `dfs(root, counts)` from the main function.
- Return the final `count`.

## Optimized Depth-First Search with Bitmasking
This approach improves upon the standard DFS by using a more efficient way to track the parity (odd or even) of digit counts. Instead of a full frequency array, it uses a single integer as a bitmask. This optimization makes both the path state updates and the final palindrome check faster.
**Time:** O(N), where N is the number of nodes in the tree. Each node is visited exactly once, and all operations at each node (XOR, bitwise AND) are constant time. · **Space:** O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst case of a skewed tree, H can be N, leading to O(N) space.
**Pros:** Highly efficient due to O(1) time for state updates and palindrome checks.; Uses minimal extra space for tracking path state (a single integer).; Elegant and concise implementation using bit manipulation.
**Cons:** The logic might be less intuitive for those not comfortable with bitwise operations.
### Explanation
The core idea is that to check for a pseudo-palindrome, we only need to know the parity of the counts of each digit, not the exact counts. We can use an integer, let's call it `pathMask`, to store this parity information. The `i`-th bit of `pathMask` will be 1 if the digit `i` has appeared an odd number of times in the current path, and 0 otherwise.

When we traverse to a node with value `v`, we update the mask by flipping the `v`-th bit using the XOR operator: `pathMask = pathMask ^ (1 << v)`. A path is pseudo-palindromic if at most one digit has an odd count. In terms of our bitmask, this means `pathMask` has at most one bit set to 1. A positive integer has at most one bit set to 1 if and only if it is zero or a power of two. This can be checked with a clever bitwise trick: `(pathMask & (pathMask - 1)) == 0`.

This method is more efficient as updating the state and checking the condition at leaves are both single, fast O(1) operations.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int count = 0;

    public int pseudoPalindromicPaths (TreeNode root) {
        dfs(root, 0);
        return count;
    }

    private void dfs(TreeNode node, int pathMask) {
        if (node == null) {
            return;
        }

        // Update the path mask with the current node's value
        pathMask ^= (1 << node.val);

        // If it's a leaf node, check for pseudo-palindrome
        if (node.left == null && node.right == null) {
            // Check if at most one bit is set in the mask
            if ((pathMask & (pathMask - 1)) == 0) {
                count++;
            }
        } else {
            // Continue traversal
            dfs(node.left, pathMask);
            dfs(node.right, pathMask);
        }
        // No explicit backtracking is needed for the mask, as it's passed by value.
    }
}
```
### Algorithm
- Initialize a global or member variable `count` to 0.
- Define a recursive DFS function, `dfs(node, pathMask)`, where `pathMask` is an integer used as a bitmask.
- In the `dfs` function:
  - If the current `node` is null, return.
  - Update the `pathMask` by flipping the bit corresponding to the node's value. This is done with an XOR operation: `pathMask ^= (1 << node.val)`.
  - Check if the current node is a leaf node (`node.left == null && node.right == null`).
    - If it is a leaf, check if the `pathMask` represents a pseudo-palindromic path. This is true if `pathMask` has at most one bit set to 1. This can be checked efficiently with the bitwise trick: `(pathMask & (pathMask - 1)) == 0`.
    - If the condition is true, increment `count`.
  - If it's not a leaf node, recursively call the function for the left and right children, passing the updated `pathMask`: `dfs(node.left, pathMask)` and `dfs(node.right, pathMask)`.
- Start the traversal by calling `dfs(root, 0)` from the main function. The initial mask is 0 as the path is empty.
- Return the final `count`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int pseudoPalindromicPaths ( TreeNode root ) { return dfs ( root , 0 ); } private int dfs ( TreeNode root , int mask ) { if ( root == null ) { return 0 ; } mask ^= 1 << root . val ; if ( root . left == null && root . right == null ) { return ( mask & ( mask - 1 )) == 0 ? 1 : 0 ; } return dfs ( root . left , mask ) + dfs ( root . right , mask ); } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int pseudoPalindromicPaths ( TreeNode * root ) { function < int ( TreeNode * , int ) > dfs = [ & ]( TreeNode * root , int mask ) { if ( ! root ) { return 0 ; } mask ^= 1 << root -> val ; if ( ! root -> left && ! root -> right ) { return ( mask & ( mask - 1 )) == 0 ? 1 : 0 ; } return dfs ( root -> left , mask ) + dfs ( root -> right , mask ); }; return dfs ( root , 0 ); } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def pseudoPalindromicPaths ( self , root : Optional [ TreeNode ]) -> int : def dfs ( root : Optional [ TreeNode ], mask : int ): if root is None : return 0 mask ^= 1 << root . val if root . left is None and root . right is None : return int (( mask & ( mask - 1 )) == 0 ) return dfs ( root . left , mask ) + dfs ( root . right , mask ) return dfs ( root , 0 )
```