Pseudo-Palindromic Paths in a Binary Tree

Problem

Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.

Return the number of pseudo-palindromic paths going from the root node to leaf nodes.

Examples

Example 1:

graph TD
    A(2)
    B(3)
    C(1)
    D(3)
    E(1)
    F(1)

    A --- B
    A --- C
    B --- D
    B --- E
    C ~~~ N1:::hidden
    C --- F


classDef hidden display:none
linkStyle 0 stroke:red,stroke-width:4px
linkStyle 2 stroke:red,stroke-width:4px
linkStyle 1 stroke:lightgreen,stroke-width:4px
linkStyle 5 stroke:lightgreen,stroke-width:4px

Input: root = [2,3,1,3,1,null,1]
Output: 2 
Explanation: 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:

graph TD
    A(2)
    B(1)
    C(1)
    D(1)
    E(3)
    F(1)

    A --- B & C
    B --- D & E
    E ~~~ N1:::hidden
    E --- F


classDef hidden display:none
linkStyle 0 stroke:lightgreen,stroke-width:4px
linkStyle 2 stroke:lightgreen,stroke-width:4px

Input: root = [2,1,1,1,3,null,null,null,null,null,1]
Output: 1 
Explanation: 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

Solution

Method 1 - Using Set and DFS

A palindromic string can have either:

• Odd length: All characters appear an even number of times, except one which appears an odd number of times.
• Even length: All characters appear an even number of times.

Algorithm

1. Traverse on Tree with root.
2. If node val exists in set, remove it; else add it. Consider the path: 1→1, then we have set size of 0, as even nodes cancel each other out. If it is 1→1→1 then we have just value remaining in set.
3. At the leaf node, check if the size of set <= 1. If the set size is less than 1, then we have found 1 palindromic path
4. Continue till we find all the paths

Code

Java

class Solution {
    public int pseudoPalindromicPaths(TreeNode root) {
        return dfs(root, new HashSet<>());
    }

    private int dfs(TreeNode curr, Set<Integer> numSet) {
        if (curr == null) return 0;

        // Toggle current node value in the set
        if (numSet.contains(curr.val)) {
            numSet.remove(curr.val);
        } else {
            numSet.add(curr.val);
        }

        // If it's a leaf node, check for pseudo-palindrome condition
        if (curr.left == null && curr.right == null) {
            return numSet.size() <= 1 ? 1 : 0;
        }

        // Continue DFS for both left and right subtrees
        int leftPaths = dfs(curr.left, new HashSet<>(numSet));
        int rightPaths = dfs(curr.right, new HashSet<>(numSet));
        
        return leftPaths + rightPaths;
    }
}

Python

class Solution:
    def pseudoPalindromicPaths(self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode], numSet: Set[int]) -> int:
            if not node:
                return 0

            # Toggle the value in the set
            if node.val in numSet:
                numSet.remove(node.val)
            else:
                numSet.add(node.val)

            # Check if it's a leaf node
            if not node.left and not node.right:
                return 1 if len(numSet) <= 1 else 0

            # Recursively evaluate left and right child nodes
            left_paths = dfs(node.left, set(numSet))
            right_paths = dfs(node.right, set(numSet))

            return left_paths + right_paths

        return dfs(root, set())

Complexity

• Time: O(n), where n is the number of nodes, as all the nodes are traversed only once.
• Space: O(k + h), where k is the number of different elements, h is the height.

Method 2 - Using an Integer bitmask

To determine the number of pseudo-palindromic paths, we need to check for paths where the node values can form at least one permutation that is a palindrome. For a sequence to potentially form a palindrome:

1. At most one digit can have an odd count while all others must have even counts.

Here is the approach:

1. Binary Tree Traversal: Perform a Depth-First Search (DFS) traversal from the root to leaf nodes.
2. Frequency Count via Mask: Use a bitmask to track the count of digits. Each bit position corresponds to the digits 1 to 9. Flip the bits as you encounter digits in the path.
3. Check Palindromic Condition: At a leaf node, the path is pseudo-palindromic if the bitmask has at most one bit set (x & (x - 1) == 0).
4. Return Count: Increment the counter for pseudo-palindromic paths.

Code

Java

class Solution {
    public int pseudoPalindromicPaths(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode node, int mask) {
        if (node == null) return 0;

        // Update bitmask for current digit
        mask ^= (1 << node.val);

        // Leaf node check
        if (node.left == null && node.right == null) {
            return (mask & (mask - 1)) == 0 ? 1 : 0;
        }

        // Recursive calls to both children and summing their results
        return dfs(node.left, mask) + dfs(node.right, mask);
    }
}

Python

class Solution:
    def pseudoPalindromicPaths(self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode], mask: int) -> int:
            if not node:
                return 0

            # Update bitmask for current digit
            mask ^= (1 << node.val)

            # Check for leaf node and return 1 if pseudo-palindromic
            if not node.left and not node.right:
                return 1 if (mask & (mask - 1)) == 0 else 0

            # Sum results of recursive calls
            return dfs(node.left, mask) + dfs(node.right, mask)

        return dfs(root, 0)

Complexity

• Time: O(n) for the DFS traversal, where n is the number of nodes.
• Space: O(h) as the recursion stack takes space proportional to the height of the tree.