Approach 1: Depth-First Search
As we do a pre-order traversal, we will flip nodes on the fly to try to match our voyage with the given one.
If we are expecting the next integer in our voyage to be
voyage[i], then there is only at most one choice for path to take, as all nodes have different values.
Do a depth first search. If at any node, the node's value doesn't match the voyage, the answer is
Otherwise, we know when to flip: the next number we are expecting in the voyage
voyage[i] is different from the next child.
Time Complexity: , where is the number of nodes in the given tree.
Space Complexity: .
Analysis written by: @awice.