Pseudo-Palindromic Paths in a Binary Tree
Medium · Graphs · Explanation and code example
Iterative DFS
How it works
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.
Steps
- 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.
- Pop
- Return the count.
Complexity
- Time complexity:
O(n) - Space complexity:
O(h)
Where
nis the number of nodes andhis the height of the given tree.
Things to watch for
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.
Python code example
from typing import Optional
# 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
C++ code example
/**
* 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) {
stack<pair<TreeNode*, int>> s;
s.push({root, 0});
int count = 0;
while (!s.empty()) {
auto [node, path] = s.top();
s.pop();
path ^= (1 << node->val);
if (!node->left && !node->right) {
if ((path & (path - 1)) == 0) count++;
} else {
if (node->right) s.push({node->right, path});
if (node->left) s.push({node->left, path});
}
}
return count;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.