Skip to main content
Talentd

Count Paths That Can Form a Palindrome in a Tree - Solution & Explanation

HardDynamic ProgrammingBit ManipulationTreeDepth-First Search11 min readAsked at: Uber, Google, Thoughtspot +1
Practice this problem

Problem Statement

You are given a tree (i.e. a connected, undirected graph that has no cycles) rooted at node 0 consisting of n nodes numbered from 0 to n - 1. The tree is represented by a 0-indexed array parent of size n, where parent[i] is the parent of node i. Since node 0 is the root, parent[0] == -1.

You are also given a string s of length n, where s[i] is the character assigned to the edge between i and parent[i]. s[0] can be ignored.

Return the number of pairs of nodes (u, v) such that u < v and the characters assigned to edges on the path from u to v can be rearranged to form a palindrome.

A string is a palindrome when it reads the same backwards as forwards.

 

Example 1:

Input: parent = [-1,0,0,1,1,2], s = "acaabc"
Output: 8
Explanation: The valid pairs are:
- All the pairs (0,1), (0,2), (1,3), (1,4) and (2,5) result in one character which is always a palindrome.
- The pair (2,3) result in the string "aca" which is a palindrome.
- The pair (1,5) result in the string "cac" which is a palindrome.
- The pair (3,5) result in the string "acac" which can be rearranged into the palindrome "acca".

Example 2:

Input: parent = [-1,0,0,0,0], s = "aaaaa"
Output: 10
Explanation: Any pair of nodes (u,v) where u < v is valid.

 

Constraints:

  • n == parent.length == s.length
  • 1 <= n <= 105
  • 0 <= parent[i] <= n - 1 for all i >= 1
  • parent[0] == -1
  • parent represents a valid tree.
  • s consists of only lowercase English letters.

Approach Overview

Problem Overview: You are given a rooted tree where each edge contributes a character. The task is to count pairs of nodes whose path characters can be rearranged to form a palindrome. A path can form a palindrome if at most one character appears an odd number of times.

Approach 1: Brute Force Path Frequency Check (O(nĀ² * 26) time, O(n) space)

Enumerate every pair of nodes and reconstruct the path between them. Track character frequencies along the path and verify whether the counts allow a palindrome (no more than one odd frequency). This requires computing paths repeatedly, typically using parent pointers or LCA preprocessing. While straightforward conceptually, checking all pairs makes the approach quadratic and too slow for large trees.

Approach 2: DFS with Bitmask for Palindrome Check (O(n * 26) time, O(n) space)

The optimal solution relies on parity instead of full frequency counts. Maintain a 26-bit mask while running Depth-First Search. Each bit represents whether the count of a character along the current root-to-node path is odd or even. Toggle the corresponding bit when traversing an edge. Two nodes form a valid palindrome path if the XOR of their masks has either zero bits set or exactly one bit set. Use a hash map to store how many times each mask has appeared so far. For each node, add counts of matching masks (same mask or masks differing by one bit). This turns the palindrome condition into fast bit operations using bit manipulation. Because each node checks at most 26 toggled variants, the total complexity remains linear.

Approach 3: Dynamic Programming on Tree (O(n * 26) time, O(n) space)

This approach frames the same idea as a tree DP. While traversing the tree, propagate the current parity mask from parent to child. Maintain a frequency map of masks seen on the path from the root to the current node. Each node queries the map for identical masks and masks differing by one bit to count valid pairs ending at that node. The DP interpretation emphasizes accumulating results as the traversal progresses while avoiding recomputation across subtrees.

Recommended for interviews: DFS with bitmask parity is the expected solution. The brute force approach shows you understand the palindrome condition, but the bitmask trick demonstrates strong problem-solving and knowledge of parity compression with XOR operations.

Approach 1: DFS with Bitmask for Palindrome Check

We can use a Depth First Search (DFS) approach combined with a bitmask to efficiently determine if the characters along a path can be rearranged into a palindrome. The idea is as follows:

  • Use DFS to traverse the tree, calculating a bitmask at each node that represents the parity (odd/even) of the counts of characters encountered along the path from the root.
  • The bitmask at a node will toggle at the bit position corresponding to the character being traversed.
  • When considering the path between two nodes, the XOR of their bitmasks will give the character frequency parity for that path.
  • If the result is zero or a power of two, then the path can be rearranged to form a palindrome.
  • To optimize, use a hashmap to count pairs of nodes with equal bitmasks and those differing by one bit.

This Python solution uses DFS to navigate through the tree starting from the root node. We maintain a bitmask `path` that helps track character parity. For any given node to node path within the tree, the XOR of their paths determines if the characters can form a palindrome. The usage of memoization via the `memo` dictionary helps in efficiently checking these conditions for all node pairs.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n), where n is the number of nodes because each node and each edge in the tree is visited once.
Space Complexity: O(n), for storing the tree structure and the memoization dictionary.

Try this approach in the editor ā†’

Approach 2: Dynamic Programming on Tree

Another approach to solve this problem is using dynamic programming on trees. The idea is to precompute some information at each node that helps in determining the palindromic nature of any two nodes quickly.

  • Precompute the character frequency from root to each node during DFS.
  • For any two nodes, determine the character frequency between them using precomputed data to see if they can form a palindrome.
  • This approach, however, can be inefficient in time complexity in dense trees, making the bit manipulation method preferred for larger constraints.

The Java solution uses dynamic programming to calculate character frequency masks for each node. This mask is then used to determine palindromic potential between any two nodes. While dynamic programming is used, the main palindromic check still hinges on bit manipulation to quickly assess parity conditions between nodes.

Code

JavaC#

Java

C#

Complexity

Time Complexity: Although we precompute data, combining this with the mask checking gives an overall complexity similar to O(n^2).
Space Complexity: O(n), for storing precomputed masks and the map of frequency masks.

Try this approach in the editor ā†’

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
DFS with Bitmask for Palindrome Check

Time Complexity: O(n), where n is the number of nodes because each node and each edge in the tree is visited once.
Space Complexity: O(n), for storing the tree structure and the memoization dictionary.

Dynamic Programming on Tree

Time Complexity: Although we precompute data, combining this with the mask checking gives an overall complexity similar to O(n^2).
Space Complexity: O(n), for storing precomputed masks and the map of frequency masks.

Default Approachā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Path Frequency CheckO(nĀ² * 26)O(n)Useful for understanding the palindrome condition or validating small inputs
DFS with Bitmask ParityO(n * 26) ā‰ˆ O(n)O(n)Best general solution; uses parity masks and hash lookups for fast counting
Dynamic Programming on TreeO(n * 26)O(n)Alternative formulation when solving tree problems using DP patterns

Video Solution

2791. Count Paths That Can Form a Palindrome in a Tree | O(N^3) - O(N*N) - O(N) |Leetcode Weekly 355 ā€¢ codingMohan ā€¢ 4,140 views views

Watch 8 more video solutions ā†’

Frequently Asked Questions

Is Count Paths That Can Form a Palindrome in a Tree easy or hard?
The problem is classified as Hard because it combines tree traversal, bit manipulation, and prefix-style counting. The key difficulty is recognizing that palindrome feasibility depends only on parity, allowing the path state to be compressed into a bitmask.
How to solve Count Paths That Can Form a Palindrome in a Tree in O(n)?
Traverse the tree using DFS while maintaining a parity bitmask for characters on the root-to-node path. Store counts of previously seen masks in a hash map. For each node, add matches with the same mask and masks with one bit flipped, since a palindrome allows at most one odd character frequency. This reduces the palindrome check to constant-time bit operations.
What is the best approach for Count Paths That Can Form a Palindrome in a Tree?
The most efficient approach uses DFS with a bitmask to track the parity of character frequencies along the path. Each node maintains a 26-bit mask where each bit indicates whether a character count is odd. Two nodes form a valid palindrome path if their masks differ by at most one bit. A hash map stores mask frequencies, giving an overall time complexity of O(n).
What data structure is used in Count Paths That Can Form a Palindrome in a Tree?
The key structures are a tree adjacency list for traversal, a hash map to count previously seen parity masks, and integer bitmasks to represent character frequency parity. DFS is used to explore nodes while updating the mask.
What is the time complexity of Count Paths That Can Form a Palindrome in a Tree?
The optimal solution runs in O(n * 26) time, which simplifies to O(n) because 26 is constant. During DFS, each node checks the current mask and up to 26 masks that differ by one bit. Space complexity is O(n) due to recursion and the mask frequency map.
Count Paths That Can Form a Palindrome in a Tree Python or Java solution approach
Both Python and Java implementations follow the same strategy: run DFS from the root, maintain a parity bitmask, and use a hash map to count matching masks. Python typically uses a dictionary for mask counts, while Java uses a HashMap<Integer, Integer>. The algorithm remains O(n) time and O(n) space.
Is Count Paths That Can Form a Palindrome in a Tree asked at Google, Amazon, or Meta?
Problems combining tree traversal with bitmask parity frequently appear in interviews at companies like Google, Amazon, and Meta. Variations of this problem test knowledge of DFS, prefix parity tricks, and efficient counting using hash maps.

Ready to solve this problem?

Practice Count Paths That Can Form a Palindrome in a Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Valid Paths in a Tree