1457. Pseudo-Palindromic Paths in a Binary Tree - Explanation

1. Depth First Search

Intuition

A path can form a palindrome if at most one digit has an odd count (that digit would go in the middle). As we traverse from root to leaf, we track the count of each digit and maintain a running count of how many digits have odd frequency. At each leaf, we check if the odd count is at most 1.

Algorithm

Initialize a frequency map for digits (1-9) and an odd counter.
Define dfs(node):
- If null, return 0.
- Increment the count for node.val. Update odd accordingly (increment if count became odd, decrement if it became even).
- If it is a leaf node, return 1 if odd <= 1, else 0.
- Otherwise, recurse on both children and sum results.
- Before returning, undo the changes (decrement count, restore odd).
Return dfs(root).

# 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
class Solution:
    def pseudoPalindromicPaths(self, root: Optional[TreeNode]) -> int:
        count = defaultdict(int)
        odd = 0

        def dfs(cur):
            nonlocal odd
            if not cur:
                return 0

            count[cur.val] += 1
            odd_change = 1 if count[cur.val] % 2 == 1 else -1
            odd += odd_change

            if not cur.left and not cur.right:
                res = 1 if odd <= 1 else 0
            else:
                res = dfs(cur.left) + dfs(cur.right)

            odd -= odd_change
            count[cur.val] -= 1
            return res

        return dfs(root)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(h)$ for recursion stack.

Where $n$ is the number of nodes and $h$ is the height of the given tree.

2. Depth First Search (Using Array)

Intuition

Instead of a hash map, we use a fixed-size array since node values are limited to 1-9. We track odd/even counts using XOR: toggling a bit each time a digit appears. This gives a cleaner way to track parity while maintaining the same core logic of counting odd-frequency digits.

Algorithm

Create an array count[10] initialized to 0, and an odd counter.
Define dfs(node, odd):
- If null, return 0.
- Toggle count[node.val] using XOR. Update odd based on whether the count is now odd or even.
- If it is a leaf and odd <= 1, return 1. Otherwise recurse on children.
- Restore odd and toggle count[node.val] back before returning.
Return dfs(root, 0).

# 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
class Solution:
    def pseudoPalindromicPaths(self, root: Optional[TreeNode]) -> int:
        count = [0] * 10
        odd = 0

        def dfs(cur):
            nonlocal odd
            if not cur:
                return 0

            count[cur.val] ^= 1
            odd += 1 if count[cur.val] else -1

            if not cur.left and not cur.right and odd <= 1:
                res = 1
            else:
                res = dfs(cur.left) + dfs(cur.right)

            odd -= 1 if count[cur.val] else -1
            count[cur.val] ^= 1

            return res

        return dfs(root)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(h)$ for recursion stack.

Where $n$ is the number of nodes and $h$ is the height of the given tree.

3. Depth First Search (Bit Mask)

Intuition

We can encode all parity information in a single integer using bits. Each bit position represents a digit, and the bit is 1 if that digit has appeared an odd number of times. XOR toggles the bit on each occurrence. At a leaf, if the path is pseudo-palindromic, at most one bit should be set. We check this with the trick: path & (path - 1) == 0 (true for 0 or exactly one bit set).

Algorithm

Define dfs(node, path):
- If null, return 0.
- Toggle the bit for node.val: path ^= (1 << node.val).
- If it is a leaf, return 1 if (path & (path - 1)) == 0, else 0.
- Otherwise, return dfs(left, path) + dfs(right, path).
Call dfs(root, 0).

# 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
class Solution:
    def pseudoPalindromicPaths(self, root: Optional[TreeNode]) -> int:
        def dfs(node, path):
            if not node:
                return 0

            path ^= 1 << node.val
            if not node.left and not node.right:
                return 1 if (path & (path - 1)) == 0 else 0

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

        return dfs(root, 0)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(h)$ for recursion stack.

Where $n$ is the number of nodes and $h$ is the height of the given tree.

4. Breadth First Search

Intuition

BFS traverses level by level using a queue. We pair each node with its current path bitmask. When we reach a leaf, we check if the path can form a palindrome using the same bit trick. This approach uses more space than DFS but processes nodes in breadth-first order.

Algorithm

Initialize a queue with (root, 0).
While the queue is not empty:
- Dequeue (node, path).
- Update path ^= (1 << node.val).
- If it is a leaf, increment the count if (path & (path - 1)) == 0.
- Otherwise, enqueue children with the updated path.
Return the count.

# 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
class Solution:
    def pseudoPalindromicPaths(self, root: Optional[TreeNode]) -> int:
        res = 0
        q = deque([(root, 0)])
        while q:
            node, path = q.popleft()
            path ^= 1 << node.val

            if not node.left and not node.right:
                if path & (path - 1) == 0:
                    res += 1
                continue

            if node.left:
                q.append((node.left, path))
            if node.right:
                q.append((node.right, path))

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

5. Iterative DFS

Intuition

We can simulate recursive DFS using an explicit stack. Each stack entry contains a node and the path bitmask accumulated so far. This avoids recursion overhead and potential stack overflow for very deep trees, while maintaining the same DFS traversal order.

Algorithm

Initialize a stack with (root, 0).
While the stack is not empty:
- Pop (node, path).
- Update path ^= (1 << node.val).
- If it is a leaf, increment the count if (path & (path - 1)) == 0.
- Otherwise, push children (with updated path) onto the stack.
Return the count.

# 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
class Solution:
    def pseudoPalindromicPaths(self, root: Optional[TreeNode]) -> int:
        count = 0
        stack = [(root, 0)]
        while stack:
            node, path = stack.pop()
            path ^= (1 << node.val)

            if not node.left and not node.right:
                if path & (path - 1) == 0:
                    count += 1
            else:
                if node.right:
                    stack.append((node.right, path))
                if node.left:
                    stack.append((node.left, path))

        return count

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(h)$

Where $n$ is the number of nodes and $h$ is the height of the given tree.

Common Pitfalls

Forgetting to Backtrack State

When using DFS with a shared count array or bitmask, failing to restore the state after returning from recursive calls corrupts the path information for sibling subtrees. Always undo the toggle operation (XOR back or decrement count) before returning from the current node.

Checking Palindrome Condition at Non-Leaf Nodes

The pseudo-palindrome check should only occur at leaf nodes (where both left and right children are null). Checking at internal nodes leads to counting incomplete paths and produces incorrect results. Always verify node.left == null && node.right == null before evaluating the palindrome condition.

Misunderstanding the Palindrome Condition

A path can form a palindrome if at most one digit has an odd count (the middle element for odd-length palindromes). Using odd == 0 instead of odd <= 1 misses valid paths with odd length. The bitmask check path & (path - 1) == 0 correctly identifies zero or one bit set.