Skip to main content
Talentd

Check if DFS Strings Are Palindromes - Solution & Explanation

HardArrayHash TableStringTree14 min readAsked at: Google
Practice this problem

Problem Statement

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:

  • Iterate over each child y of x in increasing order of their numbers, and call dfs(y).
  • Add the character 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:

  • Empty the string dfsStr and call dfs(i).
  • If the resulting string 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:

  • Calling dfs(0) results in the string dfsStr = "abaaba", which is a palindrome.
  • Calling dfs(1) results in the string dfsStr = "aba", which is a palindrome.
  • Calling dfs(2) results in the string dfsStr = "ab", which is not a palindrome.
  • Calling dfs(3) results in the string dfsStr = "a", which is a palindrome.
  • Calling dfs(4) results in the string dfsStr = "b", which is a palindrome.
  • Calling 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.length
  • 1 <= n <= 105
  • 0 <= parent[i] <= n - 1 for all i >= 1.
  • parent[0] == -1
  • parent represents a valid tree.
  • s consists only of lowercase English letters.

Approach Overview

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.

Approach 1: DFS with Adjacency List

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.

Code

PythonJavaJavaScript

Python

Java

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: DFS with Inline String Building

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.

Code

CC#

C

C#

Complexity

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.

Try this approach in the editor →

Approach 3: DFS + String Hashing

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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(n) - The adjacency list and recursion stack space taken.

DFS with Inline String Building

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.

DFS + String Hashing—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS with Inline String BuildingO(n²)O(n)Useful for understanding the problem or when constraints are small
DFS with Adjacency List + Rolling HashO(n)O(n)Best general solution for large trees and interview settings

Video Solution

LeetCode ||Weekly Contest 420||Check if DFS Strings Are Palindromes||JAVA • Samad Amir • 943 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Check if DFS Strings Are Palindromes easy or hard?
LeetCode classifies this problem as Hard. It combines tree traversal, subtree indexing, and hashing for palindrome detection. The difficulty comes from avoiding repeated DFS string construction and designing an O(n) solution.
Check if DFS Strings Are Palindromes Python/Java solution
Most implementations build the tree with adjacency lists, run DFS to compute entry and exit times, and maintain prefix hash arrays. The same logic works in Python, Java, and JavaScript, while lower-level languages like C or C# may build the DFS string inline and apply hashing or direct checks.
How to solve Check if DFS Strings Are Palindromes in O(n)?
Run a DFS once to produce a global DFS order of characters and record entry and exit indices for each node's subtree. Precompute forward and reverse rolling hashes of this sequence. Each subtree corresponds to a contiguous segment, so comparing forward and reverse hash values determines whether the substring is a palindrome in O(1).
What is the best approach for Check if DFS Strings Are Palindromes?
The most efficient approach performs a single DFS traversal, records the DFS order, and uses rolling hashes to check whether each subtree segment forms a palindrome. With prefix hashes and reverse hashes, each palindrome check becomes O(1). This reduces the total complexity to O(n) time with O(n) space.
Is Check if DFS Strings Are Palindromes asked at Google/Amazon/Meta?
Tree traversal combined with hashing techniques commonly appears in interviews at large tech companies such as Google, Amazon, and Meta. Variants involving subtree queries, Euler tours, and palindrome checks are typical advanced tree problems.
What data structure is used in Check if DFS Strings Are Palindromes?
The solution relies on a tree represented with an adjacency list, depth-first search traversal, and rolling hash arrays for efficient substring comparison. Prefix hash arrays allow constant-time palindrome checks for each subtree segment.
What is the time complexity of Check if DFS Strings Are Palindromes?
The optimal solution runs in O(n) time. A single DFS builds the traversal order and computes prefix hashes, and each subtree palindrome check is constant time. A naive solution that rebuilds DFS strings for every node can take O(n²) time in the worst case.

Ready to solve this problem?

Practice Check if DFS Strings Are Palindromes with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays