**The solution is based on Preorder traversal:**

```
/*
Solution1. Iterative - Stack. time = O(n) - each node is visited once; space = O(n) - stack
Translate recursive function to stack step by step, as it is. Preorder traversal: root, left, right:
Push: root
1. Pop : curr = stack.pop()
2. Push: curr's right, if exists // RIGHT
3. Push: curr's left, if exists // LEFT
4. 1) Peek: curr's right = stack.peek() - prev // ROOT: update curr's right/left
2) curr.left = nil
Keep the above steps.
*/
func flatten1(_ root: TreeNode?) {
guard let root = root else {return}
var stack = Stack<TreeNode>()
stack.push(root)
while !stack.isEmpty() {
let curr = stack.pop()! // POP: the last pushed node
if curr.right != nil{ // PUSH: curr.right (NOTE: push curr's right first, as stack reverses execution order)
stack.push(curr.right!)
}
if curr.left != nil { // PUSH: curr.left
stack.push(curr.left!)
}
if !stack.isEmpty() {
curr.right = stack.peek() // prev - root's next: its left if its left exists; its right if its left doesn't exist
}
curr.left = nil // Don't forget this!!
}
}
/*
Solution2. Recursive - time = O(n) - each node is visited once; space = O(n) - stack
Reverse process of Pre-order: RIGHT, LEFT, ROOT (to avoid changing node's left/right for the later use)
1) Reverse Pre-order traversal: RIGHT, LEFT, ROOT (travel to right leaf first)
2) a) curr's right(next) = prev;
b) curr's left = nil
3) prev = root
*/
private var prev: TreeNode?
func flatten(_ root: TreeNode?) {
guard let root = root else {return}
flatten(root.right) // Flatten root'right tree
flatten(root.left) // Flatten root'left tree
root.right = prev // Connect root.next with the previous answer
root.left = nil
prev = root // Store root to prev, then keep recursion
}
```