Pseudo-Palindromic Paths in a Binary Tree — Solution
Pseudo-Palindromic Paths in a Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Pseudo-Palindromic Paths in a Binary Tree is a medium coding problem on depth-first search, trees and bit manipulation, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Trees, Bit Manipulation
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the root of a binary tree whose node values are digits from 1 to 9.
A root-to-leaf path is pseudo-palindromic if its values can be rearranged into a palindrome (a sequence that reads the same forwards and backwards). Return the number of pseudo-palindromic paths from the root to a leaf.
Example 1
Input: root = [2,3,1,3,1,null,1]
Output: 2
Explanation: The paths are 2-3-3, 2-3-1 and 2-1-1. 2-3-3 can become 3-2-3 and 2-1-1 can become 1-2-1; 2-3-1 cannot be rearranged into a palindrome.
Example 2
Input: root = [2,1,1,1,3,null,null,null,null,null,1]
Output: 1
Explanation: Of the paths 2-1-1, 2-1-3-1 and 2-1, only 2-1-1 (as 1-2-1) works.
Example 3
Input: root = [9]
Output: 1
Explanation: A single digit is a palindrome.
Constraints
1 <= number of nodes <= 10^51 <= Node.val <= 9
Hints for Pseudo-Palindromic Paths in a Binary Tree
Hint 1
A multiset of digits can be arranged into a palindrome exactly when at most one digit appears an odd number of times.
Hint 2
So along a path you only need each digit's count parity — nine bits.
Hint 3
Toggle bit
valon the way down; at a leaf the path qualifies when the mask has at most one set bit, i.e.mask & (mask - 1) == 0.
How to solve Pseudo-Palindromic Paths in a Binary Tree
Track, for each digit, whether it has appeared an odd number of times on the current path, as one bitmask. A path is pseudo-palindromic when at most one bit is set at its leaf.
Approach
- Walk depth-first from the root with
mask = 0. - At each node flip bit
node.val:mask ^= 1 << node.val. - At a leaf, count the path if
mask & (mask - 1) == 0(zero or one bit set). - Otherwise continue into both children with the current mask and add their counts.
Why it works
A palindrome pairs up equal values around the centre, so every value appears an even number of times except possibly one (the centre). Conversely, with at most one odd count the pairs can be placed symmetrically and the odd one in the middle. Flipping a bit per occurrence records exactly the parity of each count.
Complexity
- Time —
O(n) - Space —
O(h) for the recursion
Pitfalls
- Only root-to-leaf paths count — do not test the mask at inner nodes.
- Pass the mask by value (or undo the flip when returning); a shared mask leaks between branches.
Reference solution
Python
from typing import Optional
def pseudoPalindromicPaths(root: Optional[TreeNode]) -> int:
def walk(node, mask):
mask ^= 1 << node.val
if node.left is None and node.right is None:
return 1 if mask & (mask - 1) == 0 else 0
total = 0
if node.left:
total += walk(node.left, mask)
if node.right:
total += walk(node.right, mask)
return total
return walk(root, 0)Java
public static int pseudoPalindromicPaths(TreeNode root) {
return palWalk(root, 0);
}
static int palWalk(TreeNode node, int mask) {
mask ^= 1 << node.val;
if (node.left == null && node.right == null) return (mask & (mask - 1)) == 0 ? 1 : 0;
int total = 0;
if (node.left != null) total += palWalk(node.left, mask);
if (node.right != null) total += palWalk(node.right, mask);
return total;
}C++
int palWalk(TreeNode* node, int mask);
int pseudoPalindromicPaths(TreeNode* root) {
return palWalk(root, 0);
}
int palWalk(TreeNode* node, int mask) {
mask ^= 1 << node->val;
if (!node->left && !node->right) return (mask & (mask - 1)) == 0 ? 1 : 0;
int total = 0;
if (node->left) total += palWalk(node->left, mask);
if (node->right) total += palWalk(node->right, mask);
return total;
}JavaScript
var pseudoPalindromicPaths = function(root) {
return palWalk(root, 0);
};
var palWalk = function(node, mask) {
mask ^= 1 << node.val;
if (node.left === null && node.right === null) return (mask & (mask - 1)) === 0 ? 1 : 0;
var total = 0;
if (node.left !== null) total += palWalk(node.left, mask);
if (node.right !== null) total += palWalk(node.right, mask);
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals