Not exactly the same explanation in the video (as I didn't get it fully myself), but here is my understanding (might be wrong):

Idea: Keep track of which nodes of the tree have correctly placed children (think bool[n]). If in a permutation, all nodes have their children in the correct positions, then it is a valid DFS order.

Note: We can ignore leaf nodes as they don't have children => "Always valid".

We start by checking which nodes have correctly placed children. I.e. For each non-leaf/parent node, we check that:

• It is the parent of the node to the right of it.
• AND It is the parent of the node 2**l to the right. Where l is the level of the parent (0 being the bottom/leaf level).

After each swap, we don't need to re-check the whole tree. We can just check, for each of the two swapped nodes (w/ some exceptions for root and leaf nodes) if:

• Its two children are correctly placed (see method above).
• AND Its parent has correctly placed children.

After each swap, if at least one non-leaf node has a misplaced child, the answer is "NO", else, it's a "YES".