Pseudo-Palindromic Paths in a Binary Tree

medium tree dfs bit manipulation bitmask

Problem

Each tree node's value is 1..9. A path from root to leaf is pseudo-palindromic if its multiset of values can be rearranged into a palindrome. Count such paths.

Inputroot = [2,3,1,3,1,null,1]

Output2

Paths 2-3-3 and 2-1-1 both have at most one odd-count digit.

tree (level-order, null allowed)

def pseudo_palindromic_paths(root):
    ans = 0
    def dfs(node, mask):
        nonlocal ans
        if not node: return
        mask ^= 1 << node.val
        if not node.left and not node.right:
            if mask & (mask - 1) == 0: ans += 1
            return
        dfs(node.left, mask); dfs(node.right, mask)
    dfs(root, 0)
    return ans

function pseudoPalindromicPaths(root) {
  let ans = 0;
  function dfs(n, mask) {
    if (!n) return;
    mask ^= 1 << n.val;
    if (!n.left && !n.right) { if ((mask & (mask - 1)) === 0) ans++; return; }
    dfs(n.left, mask); dfs(n.right, mask);
  }
  dfs(root, 0);
  return ans;
}

class Solution {
    int ans = 0;
    public int pseudoPalindromicPaths(TreeNode root) { dfs(root, 0); return ans; }
    void dfs(TreeNode n, int mask) {
        if (n == null) return;
        mask ^= 1 << n.val;
        if (n.left == null && n.right == null) { if ((mask & (mask - 1)) == 0) ans++; return; }
        dfs(n.left, mask); dfs(n.right, mask);
    }
}

class Solution {
    int ans = 0;
public:
    int pseudoPalindromicPaths(TreeNode* root) { dfs(root, 0); return ans; }
    void dfs(TreeNode* n, int mask) {
        if (!n) return;
        mask ^= 1 << n->val;
        if (!n->left && !n->right) { if ((mask & (mask - 1)) == 0) ans++; return; }
        dfs(n->left, mask); dfs(n->right, mask);
    }
};

Explanation

A path can be rearranged into a palindrome exactly when at most one digit appears an odd number of times. The trick is that we don't need to count anything carefully — we just need each digit's parity (odd or even), and that fits neatly into a bitmask.

We DFS from the root carrying an integer mask. At each node we flip the bit for its value with mask ^= 1 << node.val. XOR-ing toggles that bit, so a digit seen an even number of times turns its bit back to 0, and an odd count leaves it 1.

At a leaf, the mask's set bits are exactly the digits with odd counts. The path is pseudo-palindromic if there is at most one such bit. The check mask & (mask - 1) == 0 is a classic test for "zero or one bits set" — it's true only for powers of two and zero.

Example: path 2 → 3 → 3. Flipping bit 2 once, then bit 3 twice, leaves only bit 2 set — a single odd digit, so it counts. The path 2 → 1 → 1 works the same way, giving a total of 2.

Each node is visited once and the mask is just one integer, so this is linear time with very little extra space.

Time: O(n) Space: O(h)