You are given a tree rooted at node 0, consisting of n nodes numbered from 0 to n - 1. The tree is represented by an 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 node i.
Consider an empty string dfsStr, and define a recursive function dfs(int x) that takes a node x as a parameter and performs the following steps in order:
y of x in increasing order of their numbers, and call dfs(y).s[x] to the end of the string dfsStr.Note that dfsStr is shared across all recursive calls of dfs.
You need to find a boolean array answer of size n, where for each index i from 0 to n - 1, you do the following:
dfsStr and call dfs(i).dfsStr is a palindrome, then set answer[i] to true. Otherwise, set answer[i] to false.Return the array answer.
Example 1:
Input: parent = [-1,0,0,1,1,2], s = "aababa"
Output: [true,true,false,true,true,true]
Explanation:
dfs(0) results in the string dfsStr = "abaaba", which is a palindrome.dfs(1) results in the string dfsStr = "aba", which is a palindrome.dfs(2) results in the string dfsStr = "ab", which is not a palindrome.dfs(3) results in the string dfsStr = "a", which is a palindrome.dfs(4) results in the string dfsStr = "b", which is a palindrome.dfs(5) results in the string dfsStr = "a", which is a palindrome.Example 2:
Input: parent = [-1,0,0,0,0], s = "aabcb"
Output: [true,true,true,true,true]
Explanation:
Every call on dfs(x) results in a palindrome string.
Constraints:
n == parent.length == s.length1 <= n <= 1050 <= parent[i] <= n - 1 for all i >= 1.parent[0] == -1parent represents a valid tree.s consists only of lowercase English letters.Problem Overview: You are given a rooted tree and a character assigned to each node. If you run a depth‑first search starting from any node and record the characters of nodes in its subtree in DFS order, you get a string. The task is to determine for every node whether this DFS string forms a palindrome.
The challenge is that subtree DFS strings can be large. Rebuilding the string for every node leads to repeated work. Efficient solutions reuse traversal order information and use hashing to check palindrome properties quickly.
Approach 1: DFS with Inline String Building (O(n²) time, O(n) space)
This straightforward approach performs a depth-first search starting from each node and constructs the DFS string for that subtree directly. During traversal, append the node's character to a temporary string or buffer. After the traversal finishes, check whether the resulting string is a palindrome using a two‑pointer scan from both ends.
The idea is simple but expensive. Many subtrees overlap, so the same nodes are visited repeatedly. If the tree is skewed, each DFS may traverse almost the entire structure. That pushes the total complexity to O(n²). This approach is mainly useful for understanding the problem or validating smaller inputs.
Approach 2: DFS with Adjacency List + Hashing (O(n) time, O(n) space)
The optimized method builds the tree using an adjacency list and performs a single DFS traversal. While traversing, record nodes in DFS order and compute rolling hashes for the generated sequence as well as its reverse. Subtree boundaries can be tracked using entry and exit indices during the DFS.
Once each subtree corresponds to a contiguous segment of the DFS order array, palindrome checks reduce to comparing forward and reverse hash values for that segment. Hash lookups are constant time using precomputed prefix hashes and powers. This avoids reconstructing strings entirely.
This solution combines tree traversal with a hash table style rolling hash technique. Because each node is processed once and each palindrome query is O(1), the overall complexity becomes linear.
Recommended for interviews: Start by explaining the brute force DFS string construction to demonstrate understanding of subtree traversal. Then move to the optimized hashing approach. Interviewers typically expect the single‑DFS solution because it eliminates repeated traversals and scales to large trees with O(n) processing.
Constructing the tree as an adjacency list and performing a DFS to get the string for each node, then check if the resultant string is a palindrome.
The solution constructs a tree in the form of an adjacency list and performs a DFS starting from each node to build a string. It then checks if this string is a palindrome.
Python
Java
JavaScript
Time Complexity: O(n^2) - Building the DFS string involves traversing tree nodes, resulting in each character being visited multiple times.
Space Complexity: O(n) - The adjacency list and recursion stack space taken.
Directly build the string in DFS while traversing, optimizing operations by avoiding separate recursive functions.
This C implementation builds the DFS string inline while traversing each subtree, checking if it's a palindrome simultaneously post DFS completion, leveraging dynamic list sizing.
Time Complexity: O(n^2) per node since the full depth can be recalculated multiple times.
Space Complexity: O(n) for auxiliary storage inherent in recursion and node lists.
We can use Depth-First Search (DFS) to traverse the tree and compute the entire dfsStr, while also determining the interval [l, r] for each node.
Then, we use string hashing to compute the hash values of both dfsStr and the reverse of dfsStr to check if it is a palindrome.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string s.
| Approach | Complexity |
|---|---|
| DFS with Adjacency List | Time Complexity: O(n^2) - Building the DFS string involves traversing tree nodes, resulting in each character being visited multiple times. |
| DFS with Inline String Building | Time Complexity: O(n^2) per node since the full depth can be recalculated multiple times. |
| DFS + String Hashing | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Inline String Building | O(n²) | O(n) | Useful for understanding the problem or when constraints are small |
| DFS with Adjacency List + Rolling Hash | O(n) | O(n) | Best general solution for large trees and interview settings |
LeetCode ||Weekly Contest 420||Check if DFS Strings Are Palindromes||JAVA • Samad Amir • 938 views views
Watch 3 more video solutions →Practice Check if DFS Strings Are Palindromes with our built-in code editor and test cases.
Practice on FleetCode