LeetCode #94 Binary Tree Inorder Traversal with JavaScript

Solutions to LeetCode's 94. Binary Tree Inorder Traversal
with JavaScript.

Solution 2 addresses the following follow-up.
Follow up: Recursive solution is trivial, could you do it iteratively?

Solution 1: Recursive

/** * @param {TreeNode} root * @return {number[]} */ const inorderTraversal = (root) => { let res = []; helper(root); function helper(root) { if (root != null) { helper(root.left); res.push(root.val); helper(root.right); } } return res; }; 

• Time complexity: O(n)
• Space complexity: O(n)

It's very readable when implemented with recursion.

Solution 2: Iterative

/** * @param {TreeNode} root * @return {number[]} */ const inorderTraversal2 = (root) => { let current = root; const stack = []; const res = []; while (current || stack.length) { while (current) { stack.push(current); current = current.left; } current = stack.pop(); res.push(current.val); current = current.right; } return res; }; 

• Time complexity: O(n)
• Space complexity: O(n)

1. Assign root to current node
2. Push current node to stack (Nested while)
3. Move current node to the left (Nested while)
4. Pop a node out of the stack and put it in the current node.
5. push val of current node to res array
6. Move current node to the right

The iterative solution uses a stack and is less readable than the recursive solution.