# ac solution code

• 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
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.