Pseudo-Palindromic Paths in a Binary Tree solution and explanation
9 more videos on this problem
Pseudo-Palindromic Paths in a Binary Tree - Leetcode 1457 - PythonNeetCodeIO · 13:18 · 17K views
Pseudo-Palindromic Paths in a Binary Tree | 2 Ways | Bit Magic | Leetcode 1457codestorywithMIK · 26:41 · 8K views
Pseudo-Palindromic Paths in a Binary Tree | Live Coding with Explanation | Leetcode #1457Algorithms Made Easy · 4:23 · 4K views
1457. Pseudo-Palindromic Paths in a Binary Tree | Tree | Xor | Count set bits | Bit ManipulationAryan Mittal · 28:53 · 2K views
LeetCode 1457. Pseudo-Palindromic Paths in a Binary TreeHappy Coding · 14:46 · 414 views
1457. Pseudo-Palindromic Paths in a Binary Tree || DSA || Leetcode || Daily ChallengeLeetcode Daily Challenge · 7:15 · 383 views
LeetCode 1457 - Pseudo-Palindromic Paths in a Binary Tree #leetcodeMushu · 14:48 · 223 views
1457. Pseudo-Palindromic Paths in a Binary Tree (Leetcode Medium)Programming Live with Larry · 16:58 · 187 views
Pseudo-Palindromic Paths in a Binary Tree (Leetcode 1457)Coding Interviews · 25:04 · 172 views
Leetcode 1457: Pseudo-Palindromic Paths in a Binary TreeWinson Ye · 16:25 · 141 views
The 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.
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, 105]. 1 <= Node.val <= 9
Approach overview
Problem 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.
Approach 1: Depth-First Search with Frequency Counting
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.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def pseudoPalindromicPaths(root):
count = 0
def dfs(node, path):
nonlocal count
if not node:
return
path ^= (1 << node.val)
if not node.left and not node.right:
if path & (path - 1) == 0:
count += 1
else:
dfs(node.left, path)
dfs(node.right, path)
dfs(root, 0)
return count#include <unordered_set>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int pseudoPalindromicPaths(TreeNode* root) {
unordered_set<int> counts;
return dfs(root, counts);
}
int dfs(TreeNode* node, unordered_set<int>& counts) {
if (!node) return 0;
if (counts.count(node->val)) {
counts.erase(node->val);
} else {
counts.insert(node->val);
}
if (!node->left && !node->right) {
return counts.size() <= 1 ? 1 : 0;
}
int leftPaths = dfs(node->left, counts);
int rightPaths = dfs(node->right, counts);
// Backtrack
if (counts.count(node->val)) {
counts.erase(node->val);
} else {
counts.insert(node->val);
}
return leftPaths + rightPaths;
}
};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.
Approach 2: Depth-First Search with Path Count Array
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.
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public int pseudoPalindromicPaths (TreeNode root) {
return dfs(root, new int[10]);
}
private int dfs(TreeNode node, int[] count) {
if (node == null) return 0;
count[node.val]++;
int paths = 0;
if (node.left == null && node.right == null) {
int oddCount = 0;
for (int c : count) {
if (c % 2 != 0) oddCount++;
}
if (oddCount <= 1) paths = 1;
} else {
paths += dfs(node.left, count) + dfs(node.right, count);
}
count[node.val]--;
return paths;
}
}function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
function pseudoPalindromicPaths(root) {
function dfs(node, count) {
if (!node) return 0;
count[node.val]++;
let paths = 0;
if (!node.left && !node.right) {
let oddCount = 0;
for (let c of count) {
if (c % 2 !== 0) oddCount++;
}
if (oddCount <= 1) paths = 1;
} else {
paths += dfs(node.left, count) + dfs(node.right, count);
}
count[node.val]--;
return paths;
}
return dfs(root, new Array(10).fill(0));
}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.
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.
Approach 3: DFS + Bit Manipulation
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.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function pseudoPalindromicPaths(root: TreeNode | null): number {
const dfs = (root: TreeNode | null, mask: number): number => {
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);
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func pseudoPalindromicPaths(root *TreeNode) int {
var dfs func(*TreeNode, int) int
dfs = func(root *TreeNode, mask int) int {
if root == nil {
return 0
}
mask ^= 1 << root.Val
if root.Left == nil && root.Right == nil {
if mask&(mask-1) == 0 {
return 1
}
return 0
}
return dfs(root.Left, mask) + dfs(root.Right, mask)
}
return dfs(root, 0)
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn pseudo_palindromic_paths(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
fn dfs(root: Option<Rc<RefCell<TreeNode>>>, mask: i32) -> i32 {
if let Some(node) = root {
let mut mask = mask;
let val = node.borrow().val;
mask ^= 1 << val;
if node.borrow().left.is_none() && node.borrow().right.is_none() {
return if (mask & (mask - 1)) == 0 { 1 } else { 0 };
}
return (dfs(node.borrow().left.clone(), mask)
+ dfs(node.borrow().right.clone(), mask));
}
0
}
dfs(root, 0)
}
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Pseudo-Palindromic Paths in a Binary Tree easy or hard?
The problem is rated Medium on LeetCode because it combines tree traversal with a palindrome frequency condition. The DFS part is straightforward, but recognizing the odd-frequency rule for palindromes is the key insight. Once that observation is made, the implementation becomes relatively direct.
Pseudo-Palindromic Paths in a Binary Tree Python/Java solution
Python solutions typically use DFS recursion with a list or bitmask to track digit frequencies along the path. Java implementations often use an integer array of size 10 and backtracking during recursion. Both approaches achieve O(n) time complexity and O(h) space for the recursion stack.
How to solve Pseudo-Palindromic Paths in a Binary Tree in O(n)?
Traverse the tree using depth-first search while maintaining a frequency structure (array or map) for digits on the current path. When a leaf node is reached, verify that no more than one digit has an odd count. If the condition holds, increment the valid path counter. Because each node is processed once, the overall complexity remains O(n).
What is the best approach for Pseudo-Palindromic Paths in a Binary Tree?
Depth-first search with a digit count tracker is the most common solution. While traversing from root to leaf, maintain counts of digits along the path and check if at most one digit has an odd frequency. This guarantees the digits can form a palindrome. The traversal visits each node once, resulting in O(n) time complexity.
Is Pseudo-Palindromic Paths in a Binary Tree asked at Google/Amazon/Meta?
Binary tree DFS problems with path constraints are common in interviews at companies like Amazon, Google, and Meta. This problem tests recursion, path tracking, and understanding of palindrome properties. Variants involving path sums or path validation appear frequently in technical interviews.
What data structure is used in Pseudo-Palindromic Paths in a Binary Tree?
The solution uses a binary tree traversal combined with a frequency tracking structure. Most implementations use either a fixed array of size 10 for digit counts or a hash map. The traversal itself is implemented using depth-first search with recursion or an explicit stack.
What is the time complexity of Pseudo-Palindromic Paths in a Binary Tree?
The optimal solution runs in O(n) time where n is the number of nodes in the tree. Each node is visited exactly once during DFS traversal. The space complexity is O(h) due to the recursion stack, where h is the height of the binary tree.