Pseudo-Palindromic Paths in a Binary Tree

Med

#1346Time: O(N), where N is the number of nodes in the tree. We visit each node exactly once. At each leaf node, we perform a check that takes constant time (iterating 9 times), so the overall complexity is proportional to the number of nodes.Space: O(H), where H is the height of the tree. The space is dominated by the recursion stack depth. In the worst case of a skewed tree, H can be equal to N (the number of nodes), leading to O(N) space. The frequency array uses constant O(1) space.

Patterns

Bit Manipulation

Algorithms

Depth-First Search Breadth-First Search

Data structures

Tree Binary Tree

Prompt

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.

Example 1:

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:

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

Constraints:

The number of nodes in the tree is in the range [1, 10⁵].
1 <= Node.val <= 9

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a standard Depth-First Search (DFS) to traverse the tree from the root to each leaf. During the traversal, it maintains a frequency count of the digits encountered along the current path. When a leaf node is reached, it checks if the path is pseudo-palindromic by analyzing these counts.

Algorithm

Initialize a global or member variable count to 0.
Create a frequency array counts of size 10, initialized to all zeros, to store the frequency of digits 1 through 9.
Define a recursive DFS function, let's call it dfs(node, counts).
In the dfs function:
- If the current node is null, return immediately.
- Increment the frequency of the current node's value: counts[node.val]++.
- Check if the current node is a leaf node (i.e., node.left == null && node.right == null).
  - If it is a leaf, check if the current path is pseudo-palindromic. This is done by a helper function that iterates through the counts array and counts how many digits have an odd frequency. If the number of odd-frequency digits is 0 or 1, increment the global count.
- Recursively call the function for the left and right children: dfs(node.left, counts) and dfs(node.right, counts).
- Backtrack: After the recursive calls for the children return, decrement the frequency of the current node's value: counts[node.val]--. This step is crucial to correctly reflect the path state as the traversal unwinds.
Start the traversal by calling dfs(root, counts) from the main function.
Return the final count.

Walkthrough

A path's node values can form a palindrome if at most one digit appears an odd number of times. We can implement a recursive DFS function, say dfs(node, counts), that explores the tree. The counts parameter is an array that stores the frequency of each digit (1-9) from the root to the current node.

The main function initializes a counter for pseudo-palindromic paths to zero and an empty frequency array, then calls dfs(root, counts). The key to this approach is backtracking. After visiting a node and its descendants, we must undo the change made to the frequency count for that node. This ensures that when we explore a sibling branch, the counts accurately represent the path to that sibling's parent, not the path through the previously explored cousin nodes.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    int count = 0;18 19    public int pseudoPalindromicPaths (TreeNode root) {20        int[] pathCounts = new int[10];21        dfs(root, pathCounts);22        return count;23    }24 25    private void dfs(TreeNode node, int[] pathCounts) {26        if (node == null) {27            return;28        }29 30        // Add current node to the path31        pathCounts[node.val]++;32 33        // If it's a leaf node, check for pseudo-palindrome34        if (node.left == null && node.right == null) {35            if (isPseudoPalindrome(pathCounts)) {36                count++;37            }38        } else {39            // Continue traversal40            dfs(node.left, pathCounts);41            dfs(node.right, pathCounts);42        }43 44        // Backtrack: remove current node from the path45        pathCounts[node.val]--;46    }47 48    private boolean isPseudoPalindrome(int[] counts) {49        int oddCount = 0;50        for (int i = 1; i <= 9; i++) {51            if (counts[i] % 2 != 0) {52                oddCount++;53            }54        }55        return oddCount <= 1;56    }57}

Complexity

Time

O(N), where N is the number of nodes in the tree. We visit each node exactly once. At each leaf node, we perform a check that takes constant time (iterating 9 times), so the overall complexity is proportional to the number of nodes.

Space

O(H), where H is the height of the tree. The space is dominated by the recursion stack depth. In the worst case of a skewed tree, H can be equal to N (the number of nodes), leading to O(N) space. The frequency array uses constant O(1) space.

Trade-offs

Pros

Conceptually straightforward and easy to understand.
Directly models the problem by counting frequencies, making the logic clear.

Cons

Slightly less performant than the bitmasking approach due to the overhead of iterating through the frequency array at each leaf.
Requires careful implementation of backtracking to avoid incorrect counts and to manage memory efficiently.

This approach improves upon the standard DFS by using a more efficient way to track the parity (odd or even) of digit counts. Instead of a full frequency array, it uses a single integer as a bitmask. This optimization makes both the path state updates and the final palindrome check faster.

Algorithm

Initialize a global or member variable count to 0.
Define a recursive DFS function, dfs(node, pathMask), where pathMask is an integer used as a bitmask.
In the dfs function:
- If the current node is null, return.
- Update the pathMask by flipping the bit corresponding to the node's value. This is done with an XOR operation: pathMask ^= (1 << node.val).
- Check if the current node is a leaf node (node.left == null && node.right == null).
  - If it is a leaf, check if the pathMask represents a pseudo-palindromic path. This is true if pathMask has at most one bit set to 1. This can be checked efficiently with the bitwise trick: (pathMask & (pathMask - 1)) == 0.
  - If the condition is true, increment count.
- If it's not a leaf node, recursively call the function for the left and right children, passing the updated pathMask: dfs(node.left, pathMask) and dfs(node.right, pathMask).
Start the traversal by calling dfs(root, 0) from the main function. The initial mask is 0 as the path is empty.
Return the final count.

Walkthrough

The core idea is that to check for a pseudo-palindrome, we only need to know the parity of the counts of each digit, not the exact counts. We can use an integer, let's call it pathMask, to store this parity information. The i-th bit of pathMask will be 1 if the digit i has appeared an odd number of times in the current path, and 0 otherwise.

When we traverse to a node with value v, we update the mask by flipping the v-th bit using the XOR operator: pathMask = pathMask ^ (1 << v). A path is pseudo-palindromic if at most one digit has an odd count. In terms of our bitmask, this means pathMask has at most one bit set to 1. A positive integer has at most one bit set to 1 if and only if it is zero or a power of two. This can be checked with a clever bitwise trick: (pathMask & (pathMask - 1)) == 0.

This method is more efficient as updating the state and checking the condition at leaves are both single, fast O(1) operations.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    int count = 0;18 19    public int pseudoPalindromicPaths (TreeNode root) {20        dfs(root, 0);21        return count;22    }23 24    private void dfs(TreeNode node, int pathMask) {25        if (node == null) {26            return;27        }28 29        // Update the path mask with the current node's value30        pathMask ^= (1 << node.val);31 32        // If it's a leaf node, check for pseudo-palindrome33        if (node.left == null && node.right == null) {34            // Check if at most one bit is set in the mask35            if ((pathMask & (pathMask - 1)) == 0) {36                count++;37            }38        } else {39            // Continue traversal40            dfs(node.left, pathMask);41            dfs(node.right, pathMask);42        }43        // No explicit backtracking is needed for the mask, as it's passed by value.44    }45}

Complexity

Time

O(N), where N is the number of nodes in the tree. Each node is visited exactly once, and all operations at each node (XOR, bitwise AND) are constant time.

Space

O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst case of a skewed tree, H can be N, leading to O(N) space.

Trade-offs

Pros

Highly efficient due to O(1) time for state updates and palindrome checks.
Uses minimal extra space for tracking path state (a single integer).
Elegant and concise implementation using bit manipulation.

Cons

The logic might be less intuitive for those not comfortable with bitwise operations.

Solutions

Solution

1/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int pseudoPalindromicPaths ( TreeNode root ) { return dfs ( root , 0 ); } private int dfs ( TreeNode root , int mask ) { if ( root == null ) { return 0 ; } mask ^= 1 << root . val ; if ( root . left == null && root . right == null ) { return ( mask & ( mask - 1 )) == 0 ? 1 : 0 ; } return dfs ( root . left , mask ) + dfs ( root . right , mask ); } }

1/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int pseudoPalindromicPaths ( TreeNode * root ) { function < int ( TreeNode * , int ) > dfs = [ & ]( TreeNode * root , int mask ) { if ( ! root ) { return 0 ; } mask ^= 1 << root -> val ; if ( ! root -> left && ! root -> right ) { return ( mask & ( mask - 1 )) == 0 ? 1 : 0 ; } return dfs ( root -> left , mask ) + dfs ( root -> right , mask ); }; return dfs ( root , 0 ); } };

1# 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 ( root : Optional [ TreeNode ], mask : int ): if root is None : return 0 mask ^= 1 << root . val if root . left is None and root . right is None : return int (( mask & ( mask - 1 )) == 0 ) return dfs ( root . left , mask ) + dfs ( root . right , mask ) return dfs ( root , 0 )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem