LeetCode: Binary Tree Inorder Traversal Solution

Approach

Inorder traversal's process order:

• node.left
• node
• node.right

Implementation (recursive)

1var inorderTraversal = function (root) {
2  let res = []
3
4  const recursion = node => {
5    if (!node) return
6
7    recursion(node.left)
8    res.push(node.val)
9    recursion(node.right)
10
11    return
12  }
13
14  recursion(root)
15
16  return res
17}

Implementation (iterative)

1var inorderTraversal = function (root) {
2  const res = []
3  const stack = []
4
5  for (let node = root; node !== null || stack.length !== 0; ) {
6    for (; node !== null; node = node.left) {
7      stack.push(node)
8    }
9
10    node = stack.pop()
11    res.push(node.val)
12    node = node.right
13  }
14
15  return res
16}