#1457

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Pseudo-Palindromic Paths in a Binary Tree

Count all root-to-leaf paths in a binary tree that can be rearranged to form a palindrome using bitwise state tracking.

bit manipulation tree depth first search breadth first search binary tree

Problem Statement

Given a binary tree where each node contains a digit from 1 to 9, a path from the root to any leaf is considered pseudo-palindromic if its node values can be rearranged to form a palindrome. Your task is to find all such root-to-leaf paths and count how many satisfy this condition.

Implement a function that receives the root of the binary tree and returns an integer representing the total number of pseudo-palindromic paths. For example, with root = [2,3,1,3,1,null,1], there are two pseudo-palindromic paths: [2,3,3] and [2,1,1].

Examples

Example 1

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

Output: 2

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

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

Output: 1

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

Example details omitted.

Constraints

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

Solution Approach

Use DFS with bitmask for parity tracking

Traverse the tree recursively and maintain a bitmask where the i-th bit represents whether the count of digit i along the current path is odd. Flip the bit for the current node's value as you go deeper into the tree.

Check pseudo-palindromic condition at leaf nodes

When a leaf node is reached, check the bitmask. If at most one bit is set, the path can be rearranged into a palindrome. Increment the count only for paths satisfying this condition.

Aggregate counts during recursion

Return the cumulative count of pseudo-palindromic paths from the recursive calls, summing results from left and right subtrees. This avoids extra traversal and keeps the solution linear in time complexity.

Complexity Analysis

Metric	Value
Time	\mathcal{O}(N)
Space	up to

Time complexity is O(N) since each node is visited once. Space complexity is O(H) due to recursion stack, where H is the height of the tree; bitmask storage is constant and does not affect asymptotic space.

What Interviewers Usually Probe

DFS is a natural choice for path tracking in binary trees.
Bit manipulation efficiently tracks odd/even digit counts without full frequency arrays.
Leaf nodes are critical checkpoints for validating pseudo-palindromic paths.

Common Pitfalls or Variants

Common pitfalls

Not flipping the bitmask correctly can miscount pseudo-palindromic paths.
Failing to check the condition only at leaf nodes can include incomplete paths.
Assuming multiple odd counts are acceptable will produce incorrect results.

Follow-up variants

Count pseudo-palindromic paths in an N-ary tree instead of a binary tree.
Return all the pseudo-palindromic paths instead of just the count.
Allow node values up to 15 and adapt the bitmask size accordingly.

FAQ

What defines a pseudo-palindromic path in a binary tree?

A root-to-leaf path where the node values can be rearranged into a palindrome; equivalently, at most one digit has an odd frequency.

Why is bit manipulation effective for this problem?

Because we only need to track parity of digits, flipping bits efficiently represents odd/even counts without extra memory.

Can we use BFS instead of DFS?

Yes, but DFS naturally maintains the path state using recursion, which simplifies bitmask management for pseudo-palindromic checking.

What happens if the tree has only one node?

A single-node tree always forms a pseudo-palindromic path, so the count is 1.

Does the solution scale for large trees with 10^5 nodes?

Yes, because the algorithm runs in O(N) time with O(H) space, making it efficient even for deep or large binary trees.

terminal

Solution

Solution 1: DFS + Bit Manipulation

A path is a pseudo-palindromic path if and only if the number of nodes with odd occurrences in the path is $0$ or $1$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

# 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)

Continue Practicing

#1448 count good nodes in binary tree #1361 validate binary tree nodes #1315 sum of nodes with even valued grandparent