Pre-order Traversal Skipping Marked Nodes

A tree is given as an edge list. Some nodes are marked invalid. Return the pre-order traversal of the tree that skips the invalid nodes (their children promote to attach at the nearest valid ancestor). Requirements Input: edge list defining a (possibly N-ary) tree, plus a set of node ids marked invalid. Output: pre-order traversal sequence over the valid nodes only. Children of an invalid node are visited in the position the invalid node would have been visited, in the original child order. Equivalent to deleting the invalid nodes and contracting them out of the tree, then running standard pre-order. Notes Build the adjacency list from the edge list (identify the root as the node with no incoming edge if it's a directed edge list, or pick a root if the input is undirected). Recursive DFS: visit(node) appends node to the output only if valid; then recurses into each child in order regardless of the parent's validity. This is equivalent to running a normal pre-order and filtering the visit step on the validity predicate. The "children promote" semantics fall out for free because the recursion visits children in order regardless of the parent's emission. Iterative variant: explicit stack, push children in reverse order so they pop in original order. Same validity-gated emission. Edge cases: invalid root (output starts with the root's children), all nodes invalid (empty output), tree with a single valid leaf, large tree (recursion depth — switch to iterative). Common stumbling: candidates implement an explicit "contract the tree first" pass and rebuild adjacency. That works but doubles the constants; the gated-emission DFS is the cleaner answer. Preparation Implement the recursive validity-gated DFS in under 5 minutes. Add the iterative stack version for deep trees. Verify on a 6-7 node tree by hand where the root is invalid and two interior nodes are invalid. Exact traversal contract Inputs may include n, an ordered edges list of [parent, child], an explicit root, and an invalid node list. Child order must follow the order in the edges array. Invalid nodes are omitted from the result, but their children are still traversed in the position where that invalid node would have appeared. Example: edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], root = 0, invalid = [1,6] returns [0,3,4,2,5].