# ac solution code

• Explanation

In-order: left, root, right

The basic idea is to use stack to simulate the recursion procedure:

1. Start from root, recursively travel to each passed node's left child until reach the tree's left leaf
2. Then pop to left leaf's higher level node A
3. And switch to A's right branch (Sub-process of the tree with root A.right)

Keep the above steps until the current node is null and stack is empty.

Runtime = O(n): As each node is visited once

Space = O(n)

``````    func inorderTraversal(_ root: TreeNode?) -> [Int] {
var res = [Int]()
var stack = Stack<TreeNode>()
var cur: TreeNode? = root       // Set `root` as `cur`

while cur != nil || !stack.isEmpty {// <-- !stack.isEmpty
if cur != nil {             // 1. Push cur's left branch to stack until leaf
stack.push(cur!)        // Push cur to stack
cur = cur!.left         // cur = cur.left
} else {
cur = stack.pop()       // 2. Backtrack to higher level node A (stack isn't empty, via while/if condition)
res.append(cur!.val)    // Append cur's val
cur = cur!.right        // 3. Switch to the higher node A's right branch
}
}
return res
}
``````

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