Answer: Elastic SWE Interview Question 2023 October | Trees | on-campus

Solution 1: Flatten Binary Tree — Reverse Pre-Order DFS Approach A naive approach traverses the tree pre-order, stores nodes in a list, and relinks them, taking O(N) space. We can flatten the tree in-place using a **Reverse Pre-Order DFS** traversal (Right -> Left -> Root): In a standard pre-order traversal (Root -> Left -> Right), the right child is visited last. Thus, in a reversed traversal (Right -> Left -> Root), we process the nodes in reverse order of the ...