LeetCode 1457 - Pseudo-Palindromic Paths in a Binary Tree

This problem asks us to count how many root to leaf paths in a binary tree are "pseudo-palindromic". A palindrome is a s

leetcodemediumbit-manipulationtreedepth-first-searchbreadth-first-searchbinary-tree

LeetCode Problem 1457

Difficulty: 🟡 Medium
Topics: Bit Manipulation, Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

Problem Understanding

This problem asks us to count how many root to leaf paths in a binary tree are "pseudo-palindromic".

A palindrome is a sequence that reads the same forward and backward. For example, [1,2,1] and [3,4,4,3] are palindromes. The important property of a palindrome is that at most one value may appear an odd number of times. Every other value must appear an even number of times.

A path is considered pseudo-palindromic if its values can be rearranged into a palindrome. We do not care about the original order of the values along the path. We only care about the frequency of each digit.

The tree contains digits from 1 to 9. Starting at the root, we travel downward until we reach a leaf node. For every such root to leaf path, we must determine whether the multiset of values can form a palindrome. If yes, we increment the answer.

The input is a standard binary tree. Each node has:

  • A value between 1 and 9
  • A left child
  • A right child

The output is a single integer representing the number of pseudo-palindromic root to leaf paths.

The constraints are important:

  • The tree may contain up to 10^5 nodes
  • Node values are limited to digits 1 through 9

The large node count tells us that expensive per-path operations will likely be too slow. However, the small value range of only nine possible digits strongly suggests that compact frequency tracking or bit manipulation may be useful.

There are several edge cases worth noticing immediately.

A tree with only one node is always pseudo-palindromic because a single character palindrome is valid. Extremely deep trees may cause recursion depth concerns in some languages. Paths with many distinct odd frequencies should be rejected correctly. Trees that are skewed like linked lists still must be handled efficiently.

Approaches

Brute Force Approach

The most direct approach is to explore every root to leaf path using depth first search.

For each path, we store all node values in a list. Once we reach a leaf node, we count the frequency of each digit using a hash map or array. Then we count how many digits appear an odd number of times.

If the number of odd frequencies is at most one, the path is pseudo-palindromic, so we increment the answer.

This approach is correct because it explicitly evaluates every root to leaf path according to the problem definition.

However, it is inefficient. If the tree height is large, copying and scanning path arrays repeatedly becomes expensive. In the worst case, each leaf requires scanning a path of length O(H), where H is the tree height.

With up to 10^5 nodes, we need something more efficient.

Key Insight

A path can form a palindrome if and only if at most one digit has an odd frequency.

Instead of storing full frequencies, we only need to know whether each digit currently appears an even or odd number of times.

This is perfect for bit manipulation.

We use an integer bitmask where:

  • Bit i represents whether digit i currently appears an odd number of times
  • 0 means even count
  • 1 means odd count

Whenever we visit a digit, we toggle its bit using XOR.

For example:

  • Visiting digit 3 toggles bit 3
  • Visiting digit 3 again toggles it back

At a leaf node:

  • If the mask contains zero or one set bits, the path is pseudo-palindromic

A number has at most one set bit if:

mask & (mask - 1) == 0

This makes the leaf check extremely efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(N × H) O(H) Stores full paths and recomputes frequencies
Optimal O(N) O(H) Uses bitmask parity tracking during DFS

Here:

  • N is the number of nodes
  • H is the tree height

Algorithm Walkthrough

  1. Start a depth first traversal from the root node.
  2. Maintain a bitmask representing parity of digit frequencies along the current path.
  3. When visiting a node with value v, toggle bit v:
mask ^= (1 << v)

This changes the parity of digit v.

  1. Continue recursively into the left and right subtrees while passing the updated mask.
  2. When reaching a leaf node, check whether the current mask contains at most one set bit.
mask & (mask - 1) == 0

This works because:

  • 0 has no set bits
  • Powers of two have exactly one set bit
  1. If the condition is true, increment the answer.
  2. Continue traversal until all root to leaf paths are processed.

Why it works

The algorithm maintains an invariant:

At every node, the bitmask exactly represents which digits currently have odd frequencies along the root to current-node path.

A path can form a palindrome if at most one digit has an odd count. Therefore, checking whether the mask has at most one set bit correctly determines whether the path is pseudo-palindromic.

Because every node is visited exactly once and parity updates are constant time, the algorithm is both correct and efficient.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

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

            # Toggle the bit corresponding to node.val
            mask ^= (1 << node.val)

            # Check if this is a leaf node
            if not node.left and not node.right:
                # At most one bit set
                return 1 if (mask & (mask - 1)) == 0 else 0

            return dfs(node.left, mask) + dfs(node.right, mask)

        return dfs(root, 0)

The solution uses recursive depth first search.

The mask integer stores parity information for digits encountered on the current path. Each bit corresponds to one digit value.

When we visit a node, we toggle its corresponding bit using XOR. This efficiently tracks whether the digit appears an odd or even number of times.

At a leaf node, we apply the standard bit trick:

mask & (mask - 1)

If the result is zero, the mask contains at most one set bit, meaning at most one digit has odd frequency. In that case, the path can form a palindrome.

The recursion naturally explores all root to leaf paths while maintaining path state efficiently.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pseudoPalindromicPaths(root *TreeNode) int {
    var dfs func(node *TreeNode, mask int) int

    dfs = func(node *TreeNode, mask int) int {
        if node == nil {
            return 0
        }

        // Toggle parity bit
        mask ^= (1 << node.Val)

        // Leaf node
        if node.Left == nil && node.Right == nil {
            if (mask & (mask - 1)) == 0 {
                return 1
            }
            return 0
        }

        return dfs(node.Left, mask) + dfs(node.Right, mask)
    }

    return dfs(root, 0)
}

The Go implementation closely mirrors the Python version.

Go uses nil checks instead of Python's truthiness checks. The recursive helper is declared using a function variable because Go requires named recursive closures.

Integer overflow is not a concern because only bits 1 through 9 are used.

Worked Examples

Example 1

Input:

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

The tree contains three root to leaf paths.

Path 1: [2,3,3]

Step Node Mask (Binary) Explanation
Start - 0000000000 Initial mask
Visit 2 2 0000000100 Digit 2 odd
Visit 3 3 0000001100 Digits 2 and 3 odd
Visit 3 3 0000000100 Digit 3 becomes even

Leaf reached.

Final mask has one set bit.

Valid pseudo-palindromic path.

Path 2: [2,3,1]

Step Node Mask (Binary) Explanation
Start - 0000000000 Initial mask
Visit 2 2 0000000100 Digit 2 odd
Visit 3 3 0000001100 Digits 2 and 3 odd
Visit 1 1 0000001110 Digits 1,2,3 odd

Leaf reached.

Mask has three set bits.

Not pseudo-palindromic.

Path 3: [2,1,1]

Step Node Mask (Binary) Explanation
Start - 0000000000 Initial mask
Visit 2 2 0000000100 Digit 2 odd
Visit 1 1 0000000110 Digits 1 and 2 odd
Visit 1 1 0000000100 Digit 1 becomes even

Leaf reached.

Final mask has one set bit.

Valid pseudo-palindromic path.

Final answer:

2

Example 2

Input:

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

Paths:

  1. [2,1,1]
  2. [2,1,3,1]
  3. [2,1]

Path [2,1,1]

Final parity:

  • 2 appears once
  • 1 appears twice

Only one odd count.

Valid.

Path [2,1,3,1]

Final parity:

  • 2 appears once
  • 3 appears once

Two odd counts.

Invalid.

Final answer:

1

Example 3

Input:

root = [9]

Single node path:

[9]

One odd count is allowed.

Answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O(N) Every node is visited exactly once
Space O(H) Recursive call stack depth equals tree height

The algorithm performs constant time work at each node. Bit toggling and palindrome validation both take O(1) time.

The only extra space comes from recursion depth. In the worst case of a completely skewed tree, the height may become O(N).

Test Cases

# Definition for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

sol = Solution()

# Example 1
root1 = TreeNode(2)
root1.left = TreeNode(3)
root1.right = TreeNode(1)
root1.left.left = TreeNode(3)
root1.left.right = TreeNode(1)
root1.right.right = TreeNode(1)

assert sol.pseudoPalindromicPaths(root1) == 2  # standard example

# Example 2
root2 = TreeNode(2)
root2.left = TreeNode(1)
root2.right = TreeNode(1)
root2.left.left = TreeNode(1)
root2.left.right = TreeNode(3)
root2.left.right.right = TreeNode(1)

assert sol.pseudoPalindromicPaths(root2) == 1  # one valid path

# Example 3
root3 = TreeNode(9)

assert sol.pseudoPalindromicPaths(root3) == 1  # single node tree

# All same values
root4 = TreeNode(1)
root4.left = TreeNode(1)
root4.right = TreeNode(1)
root4.left.left = TreeNode(1)

assert sol.pseudoPalindromicPaths(root4) == 2  # every path valid

# No valid paths
root5 = TreeNode(1)
root5.left = TreeNode(2)
root5.right = TreeNode(3)

assert sol.pseudoPalindromicPaths(root5) == 0  # both paths invalid

# Deep skewed tree
root6 = TreeNode(2)
root6.right = TreeNode(2)
root6.right.right = TreeNode(2)
root6.right.right.right = TreeNode(2)

assert sol.pseudoPalindromicPaths(root6) == 1  # all even counts

# Mixed frequencies
root7 = TreeNode(2)
root7.left = TreeNode(3)
root7.left.left = TreeNode(2)
root7.left.left.left = TreeNode(3)

assert sol.pseudoPalindromicPaths(root7) == 1  # two even counts

# Multiple odd frequencies
root8 = TreeNode(1)
root8.left = TreeNode(2)
root8.left.left = TreeNode(3)

assert sol.pseudoPalindromicPaths(root8) == 0  # three odd counts
Test Why
Example 1 Verifies standard multi-path behavior
Example 2 Tests selective validity among paths
Example 3 Validates single node edge case
All same values Ensures repeated toggling works correctly
No valid paths Confirms rejection logic
Deep skewed tree Tests recursion on linked-list shaped tree
Mixed frequencies Verifies even frequency handling
Multiple odd frequencies Ensures invalid masks are rejected

Edge Cases

Single Node Tree

A tree containing only one node is always pseudo-palindromic because a single value forms a palindrome by itself.

This case can expose bugs if an implementation incorrectly requires zero odd frequencies instead of allowing one odd frequency.

The implementation handles this naturally because a single set bit passes the condition:

mask & (mask - 1) == 0

Completely Skewed Tree

A tree may behave like a linked list where every node has only one child.

This creates maximum recursion depth and tests whether the algorithm still processes paths correctly without branching assumptions.

The DFS implementation works correctly because it simply follows the existing child pointers until reaching the leaf.

Paths With Multiple Odd Frequencies

A path like [1,2,3] cannot form a palindrome because all three digits appear an odd number of times.

Naive implementations sometimes incorrectly check only whether the path length is odd or even.

The bitmask approach avoids this mistake by tracking exact parity information for every digit independently. If more than one bit remains set at the leaf, the path is rejected.