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:
[1, 105].1 <= Node.val <= 9Problem Overview: You traverse a binary tree from the root to every leaf. Each path produces a sequence of digits (1–9). A path is pseudo‑palindromic if the digits can be rearranged to form a palindrome. The task is to count how many root‑to‑leaf paths satisfy this condition.
Approach 1: Depth-First Search with Frequency Counting (O(n) time, O(h) space)
Run a DFS from the root while maintaining a frequency map of digits seen along the current path. When you reach a leaf, check whether the frequency counts can form a palindrome. A sequence forms a palindrome if at most one digit has an odd count. This check requires iterating through the digit counts and verifying the odd frequency condition. DFS naturally fits the problem because each recursive call represents extending a root‑to‑leaf path. The algorithm visits each node once, giving O(n) time complexity and O(h) space for recursion depth where h is the tree height.
This approach demonstrates the core idea clearly and works well in interviews. It relies on tree traversal using depth-first search and path tracking within a binary tree.
Approach 2: Depth-First Search with Path Count Array (O(n) time, O(h) space)
Instead of a map, maintain a fixed array of size 10 to store counts for digits 1–9. When visiting a node, increment its digit count in the array. When backtracking, decrement it so the parent path remains correct. At each leaf, scan the array and count how many digits have odd frequencies. If the number of odd counts is ≤ 1, the path is pseudo‑palindromic and contributes to the answer. Using a fixed array avoids hash overhead and makes updates constant time.
This version is slightly more efficient and commonly used in competitive programming. The logic still relies on recursive traversal using DFS. With n nodes, each visited once, the time complexity stays O(n). The recursion stack still requires O(h) space.
Recommended for interviews: DFS with a count array is typically preferred. It shows that you recognize the palindrome property (≤1 odd frequency) and optimize storage with a fixed-size structure. The frequency-map approach is still valuable as a stepping stone and clearly communicates the reasoning behind pseudo‑palindromic validation. Strong candidates sometimes further optimize the parity check using bit manipulation, but the DFS counting strategy already meets optimal O(n) performance.
This approach involves traversing the tree using a depth-first search (DFS) and maintaining a frequency count of digits encountered. We check if the frequency count allows a pseudo-palindromic path by ensuring there is at most one digit with an odd count.
The solution uses a DFS approach where a 'path' is represented using a bit mask, with each bit position corresponding to the digits 1 to 9. As we traverse to each node, we toggle the corresponding bit for the node's value. At leaf nodes, we check if the bit mask represents a pseudo-palindromic path by ensuring that only one bit is set (i.e., path & (path - 1) == 0).
Time Complexity: O(N), where N is the number of nodes in the tree, since we visit each node once.
Space Complexity: O(H), where H is the height of the tree. This is due to the recursion stack used by DFS.
This approach maintains an array to count the frequencies of digits from 1 to 9 along the path. We use DFS to explore all paths from the root to leaves and check each path for pseudo-palindromic properties by counting the odd frequencies in the array.
The Java solution uses an integer array count to manage digit frequencies. During the DFS traversal, digits are incremented or decremented in the array. At leaf nodes, if there is at most one digit with an odd frequency, it contributes to the pseudo-palindromic path count.
Java
JavaScript
Time Complexity: O(N), as it processes each node once.
Space Complexity: O(H), where H is the height of the tree, due to recursion and the constant-size count array.
A path is a pseudo-palindromic path if and only if the number of nodes with odd occurrences in the path is 0 or 1.
Since the range of the binary tree node values is from 1 to 9, for each path from root to leaf, we can use a 10-bit binary number mask to represent the occurrence status of the node values in the current path. The ith bit of mask is 1 if the node value i appears an odd number of times in the current path, and 0 if it appears an even number of times. Therefore, a path is a pseudo-palindromic path if and only if mask \&(mask - 1) = 0, where \& represents the bitwise AND operation.
Based on the above analysis, we can use the depth-first search method to calculate the number of paths. We define a function dfs(root, mask), which represents the number of pseudo-palindromic paths starting from the current root node and with the current state mask. The answer is dfs(root, 0).
The execution logic of the function dfs(root, mask) is as follows:
If root is null, return 0;
Otherwise, let mask = mask \oplus 2^{root.val}, where \oplus represents the bitwise XOR operation.
If root is a leaf node, return 1 if mask \&(mask - 1) = 0, otherwise return 0;
If root is not a leaf node, return dfs(root.left, mask) + dfs(root.right, mask).
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
| Approach | Complexity |
|---|---|
| Depth-First Search with Frequency Counting | Time Complexity: O(N), where N is the number of nodes in the tree, since we visit each node once. |
| Depth-First Search with Path Count Array | Time Complexity: O(N), as it processes each node once. |
| DFS + Bit Manipulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Frequency Map | O(n) | O(h) | Clear conceptual solution when explaining palindrome frequency logic |
| DFS with Path Count Array | O(n) | O(h) | Preferred in interviews and contests due to lower overhead and constant-size storage |
Pseudo-Palindromic Paths in a Binary Tree - Leetcode 1457 - Python • NeetCodeIO • 17,123 views views
Watch 9 more video solutions →Practice Pseudo-Palindromic Paths in a Binary Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor