Pseudo-Palindromic Paths in a Binary Tree – Solution & Complexity
Solution Walkthrough
1. Recognize the Pattern
The key pattern is: root-to-leaf DFS that carries parity state instead of full frequency maps. Toggling one bit per digit lets you tell, at a leaf, whether at most one count is odd.
2. Build the Algorithm
Advance one state transition at a time. XOR the current digit into the mask before exploring children, then test the final mask only when you reach a leaf.
3. Check Edge Cases
Test empty or minimal input, skewed shapes, repeated digits that leave zero odd counts, and paths where two or more digits remain odd.
4. Solution and Complexity
Time: O(n) — every node is visited once. Space: O(h) for the recursion stack, where h is the tree height (O(n) worst case on a skewed tree).
All 7 languages below use the same DFS + bitmask idea: toggle bit digit - 1 on the way down, and at each leaf check whether mask & (mask - 1) == 0.
