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)
- Assign root to current node
- Push current node to stack (Nested while)
- Move current node to the left (Nested while)
- Pop a node out of the stack and put it in the current node.
- push val of current node to res array
- Move current node to the right
The iterative solution uses a stack and is less readable than the recursive solution.
Top comments (0)