Watch 6 video solutions for Palindromic Path Queries in a Tree, a hard level problem involving Array, String, Divide and Conquer. This walkthrough by Rajan Keshari ( CSE - IIT Dhanbad ) has 725 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an undirected tree with n nodes labeled 0 to n - 1. This is represented by a 2D array edges of length n - 1, where edges[i] = [ui, vi] indicates an undirected edge between nodes ui and vi.
You are also given a string s of length n consisting of lowercase English letters, where s[i] represents the character assigned to node i.
You are also given a string array queries, where each queries[i] is either:
"update ui c": Change the character at node ui to c. Formally, update s[ui] = c."query ui vi": Determine whether the string formed by the characters on the unique path from ui to vi (inclusive) can be rearranged into a palindrome.Return a boolean array answer, where answer[j] is true if the jth query of type "query ui vi"āāāāāāā can be rearranged into a palindrome, and false otherwise.
Example 1:
Input: n = 3, edges = [[0,1],[1,2]], s = "aac", queries = ["query 0 2","update 1 b","query 0 2"]
Output: [true,false]
Explanation:
"query 0 2": Path 0 → 1 → 2 gives "aac", which can be rearranged to form "aca", a palindrome. Thus, answer[0] = true."update 1 b": Update node 1 to 'b', now s = "abc"."query 0 2": Path characters are "abc", which cannot be rearranged to form a palindrome. Thus, answer[1] = false.Thus, answer = [true, false].
Example 2:
Input: n = 4, edges = [[0,1],[0,2],[0,3]], s = "abca", queries = ["query 1 2","update 0 b","query 2 3","update 3 a","query 1 3"]
Output: [false,false,true]
Explanation:
"query 1 2": Path 1 → 0 → 2 gives "bac", which cannot be rearranged to form a palindrome. Thus, answer[0] = false."update 0 b": Update node 0 to 'b', now s = "bbca"."query 2 3": Path 2 → 0 → 3 gives "cba", which cannot be rearranged to form a palindrome. Thus, answer[1] = false."update 3 a": Update node 3 to 'a', s = "bbca"."query 1 3": Path 1 → 0 → 3 gives "bba", which can be rearranged to form "bab", a palindrome. Thus, answer[2] = true.Thus, answer = [false, false, true].
Constraints:
1 <= n == s.length <= 5 * 104edges.length == n - 1edges[i] = [ui, vi]0 <= ui, vi <= n - 1s consists of lowercase English letters.edges represents a valid tree.1 <= queries.length <= 5 * 104āāāāāāā
queries[i] = "update ui c" orqueries[i] = "query ui vi"0 <= ui, vi <= n - 1c is a lowercase English letter.Problem Overview: You are given a tree where each node contains a character. For multiple queries, determine whether the characters along the path between two nodes can be rearranged to form a palindrome. A path is palindromic if at most one character appears an odd number of times.
Approach 1: Brute Force Path Collection (O(n) per query, O(n) space)
For every query, explicitly find the path between the two nodes using DFS or by computing the path through their Lowest Common Ancestor (LCA). Collect all characters along that path, count their frequencies using a hash map, and check if at most one character has an odd count. This approach is straightforward but inefficient because each query may traverse up to O(n) nodes. With many queries, the total runtime becomes O(n * q).
Approach 2: Prefix Bitmask with LCA (O((n + q) log n) time, O(n log n) space)
Encode character frequency parity using a bitmask. Each node stores a mask where the i-th bit represents whether the count of character i from the root to that node is odd. Compute these masks during a DFS. For a query between nodes u and v, compute the mask for the path using mask[u] XOR mask[v] XOR char(lca). A path can form a palindrome if the resulting mask has at most one bit set. LCA is computed using binary lifting on the tree. Checking the palindrome condition becomes a constant-time bit operation.
Approach 3: Heavy-Light Decomposition with Segment Tree (O((n + q) log n) time, O(n) space)
When queries require flexible path aggregation or potential updates, decompose the tree using Heavy-Light Decomposition. Each chain maps to an array segment, and a segment tree stores bitmasks representing character parity. For each query, split the path into O(log n) segments and combine masks using XOR. The final mask is checked for the single-bit condition. This approach combines tree decomposition with segment tree range queries and fits naturally with divide and conquer style tree processing.
Recommended for interviews: The prefix bitmask with LCA approach is usually expected. It demonstrates understanding of tree traversal, bit manipulation, and efficient path queries. Brute force confirms you understand the palindrome condition, but the optimized solution shows you can reduce frequency tracking to a constant-time parity check.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Path Traversal | O(n) per query | O(n) | Useful for understanding the problem or when the number of queries is very small |
| Prefix Bitmask + LCA | O((n + q) log n) | O(n log n) | Best general solution for static trees with many queries |
| Heavy-Light Decomposition + Segment Tree | O((n + q) log n) | O(n) | Preferred when path queries combine with updates or advanced tree queries |