Count Paths That Can Form a Palindrome in a Tree

Count Paths That Can Form a Palindrome in a Tree - Problem

Imagine you have a tree network where each connection (edge) is labeled with a character. Your mission is to find all pairs of nodes where the path between them contains characters that can be rearranged to form a palindrome!

You're given:

A tree with n nodes (numbered 0 to n-1) rooted at node 0
An array parent where parent[i] is the parent of node i
A string s where s[i] is the character on the edge between node i and its parent

Goal: Count all pairs (u, v) where u < v and the characters on the path from u to v can be rearranged to form a palindrome.

Key Insight: A string can form a palindrome if and only if at most one character appears an odd number of times!

Input & Output

example_1.py — Basic Tree

$ Input: parent = [-1,0,0,1,1,2], s = "abaaab"

› Output: 10

💡 Note: Tree has edges with characters a,b,a,a,b. Pairs like (0,1) have path 'a' which can form palindrome. Multiple valid pairs exist where characters can be rearranged to form palindromes.

example_2.py — Simple Chain

$ Input: parent = [-1,0,1], s = "aba"

› Output: 3

💡 Note: Tree: 0-a-1-b-2. Valid pairs: (0,1) path='a', (1,2) path='b', (0,2) path='ab'. All can form palindromes since single chars and pairs with different chars work.

example_3.py — No Valid Pairs

$ Input: parent = [-1,0,1], s = "abc"

› Output: 2

💡 Note: Tree: 0-a-1-b-2. Pairs (0,1) has path 'a', (1,2) has path 'b' - both single characters can form palindromes. Pair (0,2) has path 'ab' with 2 different odd characters, so cannot form palindrome.

Constraints

n == parent.length == s.length
1 ≤ n ≤ 10⁵
0 ≤ parent[i] ≤ n - 1 for all i ≥ 1
parent[0] == -1
parent represents a valid tree
s consists of only lowercase English letters
s[0] can be any character since it's ignored

Visualization

Tap to expand

Understanding the Visualization

Build Network Map

Convert parent array into adjacency list representing the tree structure

Start Journey

Begin DFS from root with bitmask=0, tracking character frequency parity

Check Compatibility

At each node, count paths that can combine with current path to form palindrome

Update Registry

Add current path's bitmask to hashmap for future compatibility checks

Continue Exploration

Recurse to children with updated bitmasks representing new character patterns

Key Takeaway

🎯 Key Insight: Using bitmasks to represent character frequency parity allows us to detect palindrome compatibility in O(1) time using XOR operations, making the overall solution optimal at O(n×26).

Asked in

G Google 35 a Amazon 28 f Meta 22 ⊞ Microsoft 18

The optimal solution uses DFS traversal with bitmask to represent character frequency parity. Each bit in the mask indicates if a character appears an odd number of times. Two paths can combine to form a palindrome if their masks are identical (all even counts) or differ by exactly one bit (one character with odd total count). This achieves O(n×26) time complexity with a single tree traversal.

Common Approaches

Approach	Time	Space	Notes
✓ DFS + Bitmask + HashMap (Optimal)	O(n·26)	O(n)	Use DFS with bitmask to represent character parity and count compatible paths efficiently
Brute Force (Check All Pairs)	O(n³)	O(n)	Check every pair of nodes and validate if path characters can form palindrome

DFS + Bitmask + HashMap (Optimal) — Algorithm Steps

Build adjacency list from parent array
Use bitmask to represent character frequency parity (bit i = 1 if char i appears odd times)
DFS from root, maintaining current path's bitmask
For each node, check HashMap for compatible masks (current mask and current XOR each single bit)
Add current mask count to HashMap
Compatible masks: same mask (even total for all chars) or masks differing by exactly one bit (one char appears odd times total)

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start DFS from root with mask=0, HashMap contains {0:1}

Process Node

For current mask, count compatible masks in HashMap

Update HashMap

Add current mask to HashMap for future compatibility checks

Continue DFS

Recurse to children with updated masks

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NODES 100000
#define HASH_SIZE 1000000

typedef struct Edge {
    int to, charBit;
    struct Edge* next;
} Edge;

typedef struct HashNode {
    int mask, count;
    struct HashNode* next;
} HashNode;

HashNode* hashTable[HASH_SIZE];
long long result = 0;

int hashFunc(int mask) {
    return ((long long)mask * 1000000007) % HASH_SIZE;
}

void insertHash(int mask, int count) {
    int idx = hashFunc(mask);
    HashNode* node = (HashNode*)malloc(sizeof(HashNode));
    node->mask = mask; node->count = count; node->next = hashTable[idx];
    hashTable[idx] = node;
}

int getHash(int mask) {
    int idx = hashFunc(mask);
    for (HashNode* node = hashTable[idx]; node; node = node->next) {
        if (node->mask == mask) return node->count;
    }
    return 0;
}

void updateHash(int mask, int delta) {
    int idx = hashFunc(mask);
    for (HashNode* node = hashTable[idx]; node; node = node->next) {
        if (node->mask == mask) {
            node->count += delta;
            return;
        }
    }
    insertHash(mask, delta);
}

void dfs(int node, int parentNode, int currentMask, Edge** adj) {
    result += getHash(currentMask);
    
    for (int i = 0; i < 26; i++) {
        int complementMask = currentMask ^ (1 << i);
        result += getHash(complementMask);
    }
    
    updateHash(currentMask, 1);
    
    for (Edge* e = adj[node]; e; e = e->next) {
        if (e->to != parentNode) {
            int newMask = currentMask ^ (1 << e->charBit);
            dfs(e->to, node, newMask, adj);
        }
    }
}

long long countPalindromePaths(int* parent, int parentSize, char* s) {
    int n = parentSize;
    Edge** adj = (Edge**)calloc(n, sizeof(Edge*));
    memset(hashTable, 0, sizeof(hashTable));
    result = 0;
    
    for (int i = 1; i < n; i++) {
        int charBit = s[i] - 'a';
        Edge* e1 = (Edge*)malloc(sizeof(Edge));
        e1->to = i; e1->charBit = charBit; e1->next = adj[parent[i]];
        adj[parent[i]] = e1;
        
        Edge* e2 = (Edge*)malloc(sizeof(Edge));
        e2->to = parent[i]; e2->charBit = charBit; e2->next = adj[i];
        adj[i] = e2;
    }
    
    updateHash(0, 1);
    dfs(0, -1, 0, adj);
    
    return result;
}

Time & Space Complexity

Time Complexity

⏱️

O(n·26)

O(n) for DFS traversal × O(26) for checking each possible single-bit difference

✓ Linear Growth

Space Complexity

O(n)

HashMap storing at most n different bitmask states during traversal

⚡ Linearithmic Space

34.3K Views

Medium-High Frequency

~25 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS + Bitmask + HashMap (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler