Pseudo-Palindromic Paths in a Binary Tree: Bit Manipulation on Tree Paths

Given a binary tree where each node's value is a digit from 1 to 9, count the number of root-to-leaf paths that are "pseudo-palindromic." A path is pseudo-palindromic if at least one permutation of the node values along the path forms a palindrome. In other words, at most one value can appear an odd number of times.

This is LeetCode 1457: Pseudo-Palindromic Paths in a Binary Tree.

Why this problem matters

This problem sits at the intersection of two fundamental patterns: tree traversal and bit manipulation. On the surface it looks like a counting problem on trees, but the real challenge is figuring out how to efficiently track whether a path's values can form a palindrome. If you reach for a frequency array or hash map, you will get a correct solution, but you will miss the elegant bit trick that makes the check a single operation.

The underlying insight, that palindrome-permutation checking reduces to counting parity of frequencies, appears in many other problems. Once you see that parity tracking maps perfectly to XOR on a bitmask, you have a reusable tool. Problems like "Longest Awesome Substring" and "Find Longest Awesome Substring" use the exact same bitmask technique on strings instead of trees.

Learning to combine DFS with bitwise state is a skill that pays dividends across many LeetCode problems. This problem is one of the cleanest examples of that combination.

The key insight

A sequence of values can be rearranged into a palindrome if and only if at most one value has an odd frequency. Instead of maintaining a full frequency count, you can track the parity of each value's count with a single integer used as a bitmask.

For each value v along the path, toggle bit v in the mask using XOR: mask ^= (1 << v). If a value has appeared an even number of times, its bit is 0. If odd, its bit is 1. At a leaf node, the path is pseudo-palindromic when the mask has at most one bit set. You check this with the classic trick: mask & (mask - 1) == 0. This expression is true when the mask is zero (all even) or is a power of two (exactly one odd). That single bitwise check replaces what would otherwise be a loop over a frequency array.

The solution

def pseudoPalindromicPaths(root):
    count = 0

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

    dfs(root, 0)
    return count

The DFS carries a bitmask down through the tree. At each node, it XORs the corresponding bit to toggle the parity of that value's count. When the recursion reaches a leaf (no left or right child), it checks whether the accumulated mask has at most one bit set.

Notice there is no explicit backtracking step like mask ^= (1 << node.val) after the recursive calls. That is because the mask is passed by value, not by reference. Each recursive call gets its own copy of the integer, so changes in one branch do not affect sibling branches. This is one of the advantages of using an immutable integer instead of a mutable list or dictionary for tracking state during DFS.

The nonlocal count variable accumulates the total number of pseudo-palindromic paths across the entire tree. Each leaf that passes the bitmask check increments it by one.

Visual walkthrough

Let's trace through the example tree step by step. Watch how the bitmask evolves along each root-to-leaf path and how the mask & (mask - 1) check determines whether the path is pseudo-palindromic.

Two of the three paths have at most one bit set in the final mask, so the answer is 2. The path 2 -> 3 -> 1 ends with three bits set, meaning three values each appear an odd number of times, which makes palindrome rearrangement impossible.

Complexity analysis

Time is O(n) where n is the number of nodes in the tree. The DFS visits every node exactly once. At each node, the XOR operation and the leaf check are both O(1). There is no additional work per node, so the total is linear.

Space is O(h) where h is the height of the tree. The recursion stack can grow as deep as the tree's height. For a balanced tree, h = log n. For a skewed tree, h = n. The bitmask itself is a single integer, so it adds O(1) space per stack frame.

The building blocks

1. DFS with immutable state passing

def dfs(node, state):
    if not node:
        return
    new_state = transform(state, node.val)
    if is_leaf(node):
        process(new_state)
    dfs(node.left, new_state)
    dfs(node.right, new_state)

This is the pattern of carrying accumulated state downward through a tree without needing to backtrack. Because the state is an integer (or any immutable value), each recursive branch works with its own copy. You see this in problems like Path Sum, where you subtract the node value from a running target, and in this problem, where you XOR the node value into a running bitmask.

2. Bitmask parity check for palindrome permutations

can_be_palindrome = mask & (mask - 1) == 0

This one-liner checks whether a bitmask has at most one bit set. If mask is 0, all frequencies are even, and a palindrome is possible. If mask is a power of two, exactly one frequency is odd, which is still fine for a palindrome (the odd-count character goes in the middle). If more than one bit is set, mask & (mask - 1) is nonzero, meaning multiple values have odd counts and no palindrome arrangement exists. This technique is useful anywhere you need to track parity of multiple counters simultaneously.

Edge cases

• Single node tree. The root is the only leaf. The path contains one value, which always forms a palindrome. Return 1.
• All nodes have the same value. Every path has only one distinct value, so all paths are pseudo-palindromic regardless of length.
• Skewed tree (every node has only one child). There is exactly one root-to-leaf path. Run the bitmask check on that single path.
• Two distinct values alternating. If both values appear an even number of times, the path is pseudo-palindromic. If both are odd, it is not.
• Path of length 1 (root with one leaf child). Two nodes, two values. Pseudo-palindromic only if both values are the same (the XOR cancels out, giving mask = 0).

From understanding to recall

You have seen how XOR toggles parity bits and how mask & (mask - 1) checks for at most one set bit. The DFS itself is standard, and the bitmask replaces what would otherwise be a frequency array with manual backtracking. The combination is clean and efficient.

But will you remember the mask & (mask - 1) trick under pressure? Will you instinctively reach for XOR when a problem asks about parity of frequencies? These details are easy to understand in a blog post but hard to reproduce from memory in an interview. Spaced repetition is how you bridge that gap. You write the bitmask DFS from scratch at increasing intervals until the pattern is automatic. When you see "count paths with some palindrome property" in a problem statement, the XOR bitmask template flows out without hesitation.

Related posts

• Path Sum III - Another tree path problem where you accumulate values along root-to-leaf paths and check a condition
• Binary Tree Maximum Path Sum - Tracks running state through tree paths, but with a different aggregation strategy
• Single Number - The foundational XOR trick for canceling pairs, the same principle that powers the bitmask parity check here

CodeBricks breaks Pseudo-Palindromic Paths into its DFS state-passing and bitmask parity-checking building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a tree-plus-bit-manipulation problem shows up in your interview, you do not think about it. You just write it.