Pseudo-Palindromic Paths in a Binary Tree

N-Queens

Binary Tree Zigzag Level Order Traversal

Count root-to-leaf paths whose digits can be rearranged to form a palindrome.

Given the `root` of a binary tree where each node stores a digit from `1` to `9`, a root-to-leaf path is called **pseudo-palindromic** if you can rearrange the digits on that path to form a palindrome.

A sequence can be rearranged into a palindrome when **at most one digit appears an odd number of times**.

Return the number of pseudo-palindromic root-to-leaf paths.

**Input / output**
- Input: `root: TreeNode` (JSON test fixture is a LeetCode-style level-order array, e.g. `[2,3,1,3,1,null,1]`, with `null` for a missing child)
- Output: `int`

## Example 1
```json
Input: {"root":[2,3,1,3,1,null,1]}
Output: 2
```
The paths `2 -> 3 -> 3` and `2 -> 1 -> 1` are pseudo-palindromic.

## Example 2
```json
Input: {"root":[2,1,1,1,3,null,null,null,null,null,1]}
Output: 1
```
Only the path `2 -> 1 -> 1` can be rearranged into a palindrome.

## Example 3
```json
Input: {"root":[]}
Output: 0
```

## Constraints
- 0 <= number of nodes <= 100,000
- 1 <= node.val <= 9

## Follow-up
How would you adapt the solution if values were not limited to digits `1` through `9`, so a fixed 9-bit mask was no longer enough?

The key pattern is: root-to-leaf DFS that carries parity state instead of full frequency maps. Toggling one bit per digit lets you tell, at a leaf, whether at most one count is odd.

Recognize the Pattern

Advance one state transition at a time. XOR the current digit into the mask before exploring children, then test the final mask only when you reach a leaf.

Build the Algorithm

Test empty or minimal input, skewed shapes, repeated digits that leave zero odd counts, and paths where two or more digits remain odd.

Check Edge Cases

Time: O(n) — every node is visited once. Space: O(h) for the recursion stack, where h is the tree height (O(n) worst case on a skewed tree).

All 7 languages below use the same DFS + bitmask idea: toggle bit `digit - 1` on the way down, and at each leaf check whether `mask & (mask - 1) == 0`.