FastPrepValidate a DFS Traversal Order
Problems/Validate a DFS Traversal Order

Validate a DFS Traversal Order

Rippling logoRippling● MediumNEW GRADOA
QuestionFunctionExamplesConstraints

Problem statement

Source note: The reports ask which traversal can result from DFS starting at zero. The pictured graph and options are preserved. A variable graph, complete-preorder interpretation, arbitrary neighbor order, interface and bounds complete the practice version; source match is about 90%. The highlighted screenshot choice is not a valid DFS order.

Given a connected, simple, undirected graph on vertices 0 through n-1, determine whether order can be the complete DFS preorder starting at vertex 0.

A recursive DFS records a vertex when first visiting it, then explores each unvisited neighbor fully before returning. Each vertex may choose any order for its neighbors. Return true if some choices produce exactly the supplied order. Return false for a wrong length, repeated or out-of-range vertex, or a different starting vertex.

Function

isValidDfsOrder(n: int, edges: int[][], order: int[]) → boolean

Examples

Example 1

n = 10edges = [[0,5],[5,1],[5,4],[1,8],[4,9],[4,7],[4,2],[2,3],[2,6]]order = [0,5,1,8,4,7,9,2,3,6]return = true

Finish vertex 1 and its child 8 before returning to 5, then explore the entire subtree of 4.

Example 2

n = 10edges = [[0,5],[5,1],[5,4],[1,8],[4,9],[4,7],[4,2],[2,3],[2,6]]order = [0,8,1,5,4,7,9,2,3,6]return = false

Vertex 0 has only neighbor 5, so vertex 8 cannot be visited second.

Example 3

n = 4edges = [[0,1],[0,2],[1,3],[2,3]]order = [0,1,2,3]return = false

From vertex 1, unvisited neighbor 3 must be explored before returning toward vertex 2.

Constraints

  • 1 <= n <= 2000; n-1 <= edges.length <= min(10000,n*(n-1)/2).
  • Every edge has two different valid vertices; no duplicate undirected edge exists, and the graph is connected.
  • 0 <= order.length <= 2001; each order entry is a signed 32-bit integer.

More Rippling problems

  • Stateful Log Transform and SearchPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Dependency-Aware Task SchedulerPHONE SCREEN · Seen Nov 2026
  • Filter, Sort, and Deduplicate Scheduled TasksPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
All Rippling interview questionsSee Rippling hiring insights
Saved
public boolean isValidDfsOrder(int n, int[][] edges, int[] order) {
    // Write your code here.
}
Checking account…