Palindrome Path Queries on Rooted Tree | Dataford Interview Questions

Given a rooted tree whose edges are labelled with lowercase letters, answer Q queries: does the path from the root to the given node form a palindrome? Target O(N+Q). Asked in the DSA round stage. The interviewer expected an O(N+Q) solution. Use the tree_nodes and palindrome_queries tables.

Output

Return one row per query with query_id, node_id, and is_palindrome.
Include only queried nodes reachable from the root.
Order by query_id ascending.

Schema

tree_nodes

Column	Type	Description
node_idPK	INT	Unique identifier of the tree node
parent_id	INT	Parent node identifier, or NULL for the root
edge_label	VARCHAR(1)	Lowercase label on the edge from the parent, or NULL for the root

palindrome_queries

Column	Type	Description
query_idPK	INT	Unique identifier of the query
node_id	INT	Node whose root path must be checked

Your question is Palindrome Path Queries on Rooted Tree. Start with the requirements and the two tables in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem