Skip to main content
Talentd

Pseudo-Palindromic Paths in a Binary Tree - Solution & Explanation

MediumBit ManipulationTreeDepth-First SearchBreadth-First Search18 min readAsked at: Amazon, Bcg
Practice this problem

Problem Statement

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.

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).

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

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.

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.

Code

JavaJavaScript

Java

JavaScript

Complexity

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.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(H), where H is the height of the tree. This is due to the recursion stack used by DFS.

Depth-First Search with Path Count Array

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.

DFS + Bit Manipulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS with Frequency MapO(n)O(h)Clear conceptual solution when explaining palindrome frequency logic
DFS with Path Count ArrayO(n)O(h)Preferred in interviews and contests due to lower overhead and constant-size storage

Video Solution

Pseudo-Palindromic Paths in a Binary Tree - Leetcode 1457 - Python • NeetCodeIO • 17,361 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Pseudo-Palindromic Paths in a Binary Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Divide Two Integers

Next

Add Binary