Domain 2MediumMEDIUM

Pseudo-Palindromic Paths in a Binary Tree

Count root-to-leaf paths where node values can form a palindrome using DFS and bitmask parity tracking to achieve O(N) time complexity.

Domain: medium•Updated: 2026-09-16
#DFS#Bit Manipulation#O(N)#Stack

Problem Breakdown

We need to count the number of valid paths from the root down to any leaf. A path is considered pseudo-palindromic if its node values can be rearranged into a palindrome. This condition implies that at most one digit in the sequence must appear an odd number of times (all others even).

  • Input: TreeNode root, where each value is between 1 and 9.
  • Output: Integer count of valid paths.
  • Constraints: Number of nodes up to 10510^5. Node values strictly positive single digits.

Intuition

A brute-force approach collecting all path arrays would be inefficient (O(N⋅L)O(N \cdot L) or worse). The key insight is that a sequence can form a palindrome if and only if the count of odd-frequency elements is ≤1\le 1. Since node values are small (1-9), we don’t need an array to track counts. We can use Bit Manipulation:

  • Maintain a bitmask where the ii-th bit represents whether digit (i+1)(i+1) has appeared an odd number of times on the current path.
  • Use XOR (^) to toggle bits as we traverse: mask ^= (1 << val).
  • At any leaf, check if the mask has 0 or exactly one set bit using population count logic.

Approach

  1. DFS Traversal: Perform a Depth-First Search starting from the root with an initial parity mask of 0.
  2. State Update: For each node visited, update the current path’s mask by XORing it with (1 << node.val). This flips the bit corresponding to that digit, tracking odd/even counts implicitly.
  3. Leaf Check: When reaching a leaf (no left or right children), check if bin(mask).count('1') <= 1. If true, increment valid path count; otherwise, it’s invalid for this branch.
  4. Accumulation: Sum the results from recursive calls on left and right subtrees to propagate counts up to the root call.

Complexity Analysis

  • Time Complexity: O(N)O(N) where NN is the number of nodes. We visit each node exactly once. Bitwise operations are constant time relative to machine word size (max 9 bits set).
  • Space Complexity: O(H)O(H) where HH is the height of the tree due to recursion stack usage. In a skewed tree, this degrades to O(N)O(N). Note: For Python specifically with deep trees (N=105N=10^5), sys.setrecursionlimit may be required to prevent RecursionError on worst-case inputs.

Solution

import sys

# Increase recursion depth for safety given constraints up to 10^5 nodes in skewed trees
if hasattr(sys, 'setrecursionlimit'):
    sys.setrecursionlimit(2 * 10**6) 

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):
        """
        :type root: TreeNode
        :rtype: int
        """
        
        # Helper DFS function tracking the parity mask of digits encountered on path.
        # Mask bit i is set if digit (i+1) has appeared an odd number of times.
        def dfs(node, current_mask):
            if not node:
                return 0
            
            # Toggle the bit corresponding to the current node's value.
            # Since values are 1-9, we can use bits directly or shift by val-1. 
            # Using (1 << node.val) sets a unique high-order bit for each digit 1..9 safely within integer limits.
            new_mask = current_mask ^ (1 << node.val)
            
            # Check if leaf: no children exist
            if not node.left and not node.right:
                # A palindrome permutation is possible if at most one digit has an odd count.
                # This corresponds to the mask having 0 or exactly 1 bit set.
                return bin(new_mask).count('1') <= 1
            
            # Recurse on children, accumulating valid paths found in subtrees
            left_count = dfs(node.left, new_mask) if node.left else 0
            right_count = dfs(node.right, new_mask) if node.right else 0
            
            return left_count + right_count

        return dfs(root, 0)

Edge Cases Handled

  • Single Node Tree: The recursion hits the leaf condition immediately. new_mask has exactly one bit set (the root’s value). Count is 1. Correctly returns 1.
  • Empty Path Logic: Constraints ensure at least one node exists, so we don’t handle a null root input specifically beyond standard recursion base cases (if not node).
  • Duplicate Values on Path: The XOR operation naturally handles duplicates (e.g., 2 then 2 toggles bit 1 twice, resulting in even count/0 contribution to parity), which is required for palindrome formation.
  • Deep Trees: Added sys.setrecursionlimit adjustment to handle worst-case skewed trees (O(N)O(N) depth) within Python’s standard environment constraints without hitting