Skip to main content

1457 - Pseudo-Palindromic Paths in a Binary Tree

Difficulty: Medium | Pattern: DFS + Bit Manipulation | Company tags: Amazon, Facebook

Problem Statement​

Given a binary tree where node values are digits from 1 to 9, count the number of pseudo-palindromic paths going from the root to leaf nodes.

A path is pseudo-palindromic if at most one digit has an odd count (can be rearranged into a palindrome).

Example 1:

Input: root = [2,3,1,3,1,null,1]
Output: 2
Explanation: Paths [2,3,3] and [2,1,1] are pseudo-palindromic.

Example 2:

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

Approach: DFS + Bitmask — O(n)​

Key insight: Track a bitmask where bit i is set if digit i appears an odd number of times so far. A path is pseudo-palindromic if the bitmask has at most one bit set, which means bitmask & (bitmask - 1) == 0 (standard "power of 2" check, which is True for 0 as well).

def pseudoPalindromicPaths(root) -> int:
    def dfs(node, mask):
        if not node:
            return 0
        
        mask ^= (1 << node.val)  # toggle bit for this digit
        
        if not node.left and not node.right:
            # Leaf: check if at most one odd-count digit
            return 1 if (mask & (mask - 1)) == 0 else 0
        
        return dfs(node.left, mask) + dfs(node.right, mask)
    
    return dfs(root, 0)

Algorithm Flow​

Why Bitmask Works​

Each bit represents whether a digit (1-9) has been seen an odd number of times on the current path. XOR toggles: 1 → 0 (seen twice, even count) and 0 → 1 (seen odd times).

mask & (mask - 1) == 0 checks if at most 1 bit is set (either 0 bits = all even, or exactly 1 bit = one odd).

Dry Run​

Tree: [2,3,1,3,1,null,1]

dfs(2, 0): mask = 0^(1<<2) = 0b100 = 4
  dfs(3, 4): mask = 4^(1<<3) = 0b1100 = 12
    dfs(3, 12): mask = 12^8 = 0b100 = 4 (leaf)
      4 & 3 = 0 → palindromic ✓ count=1
    dfs(1, 12): mask = 12^2 = 0b1110 = 14 (leaf)
      14 & 13 = 12 ≠ 0 → not palindromic
  dfs(1, 4): mask = 4^2 = 0b110 = 6
    dfs(1, 6): mask = 6^2 = 0b100 = 4 (leaf)
      4 & 3 = 0 → palindromic ✓ count=1

Total: 2 ✓

Complexity​

  • Time: O(n) — each node visited once
  • Space: O(h) — recursion depth

Key Terms​

TermDefinition
DFS (root-to-leaf)Recursive traversal that accumulates state along a single path and evaluates it at each leaf.
BitmaskAn integer used as a set of boolean flags; here, bit i tracks the parity (odd/even count) of digit i.
XOR togglemask ^= (1 << val) flips a bit each time the digit is seen, naturally tracking odd/even occurrences without a counter array.
Power-of-two checkmask & (mask - 1) == 0 is true only when mask has zero or one bits set — the condition for a pseudo-palindrome.
Pseudo-palindromeA multiset of values that can be reordered into a palindrome, i.e., at most one value has an odd frequency.

FAQ​

Q: Can this be solved without a hash map or count array? A: Yes — that's the point of the bitmask. Since values are digits 1-9, a single integer with 9 relevant bits replaces a Counter, making the odd/even check O(1) instead of O(9).

Q: What if the tree is empty (root = None)? A: dfs(None, mask) returns 0 immediately, so the answer is 0. No special-casing needed.

Q: What if node values weren't restricted to 1-9 (e.g., arbitrary integers)? A: A fixed-width bitmask no longer works cleanly. You'd fall back to a hash map counting parities per path, still toggled with XOR-like logic (insert/remove on backtrack), giving the same O(n) traversal but O(n) extra space instead of O(1) per call.

Q: Why does mask & (mask - 1) == 0 work for checking "at most one bit set"? A: mask - 1 flips all bits up to and including the lowest set bit. ANDing with mask clears that lowest bit. If the result is 0, either no bits were set (mask was 0) or exactly one bit was set — both valid pseudo-palindrome conditions.

Q: How would you adapt this to return the actual paths instead of a count? A: Pass a running list of node values alongside the mask, append node.val on entry and pop it on the way back up (classic backtracking), and collect the list at leaves where the mask check passes.

Quick Revision​

  • Problem: count root-to-leaf paths whose digit multiset can be rearranged into a palindrome.
  • Digits are bounded to 1-9, which makes a bitmask a natural fit for parity tracking.
  • DFS the tree, XOR-toggling bit node.val into mask at every node.
  • At a leaf, check mask & (mask - 1) == 0 — true means at most one digit has an odd count.
  • No explicit backtracking needed since mask is passed by value (not mutated in place) down each recursive call.
  • Time: O(n) — one visit per node. Space: O(h) for recursion stack, O(1) extra per call.
  • Core trick generalizes: "at most one odd count" ⇔ palindrome-rearrangeable ⇔ mask is a power of two or zero.
  • Common failure mode: forgetting to check the palindrome condition only at leaves, not at every node.
  • 112-PathSum.md — same root-to-leaf DFS accumulation pattern, but with a sum instead of a bitmask.
  • 113-PathSumII.md — root-to-leaf DFS that collects and returns full paths, useful for the "return actual paths" variant above.
  • LeetCode 266 "Palindrome Permutation" — the same mask & (mask - 1) == 0 odd-count check applied to a flat string instead of a tree path.