[Leetcode] 94. Binary Tree Inorder Traversal explained

Problem

94. Binary Tree Inorder Traversal

Approach

Recursive approach is trivial.
We can implement inorder traversal using Stack.

curNode <- root
while true:
    if curNode is null:
        if stack is empty:
            break;
        tmpNode <- stack.pop();
        add tmpNode.val to result
        curNode <- tmpNode.right;
    else:
        if curNode is not null:
            push curNode into stack
        else:
            curNode <- curNode.left;

Code

Recursive approach

/**
 * author: jooncco
 * written: 2022. 9. 8. Tue. 11:34:14 [UTC+9]
 **/

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        inorder(result, root);
        return result;
    }

    private void inorder(List<Integer> arr, TreeNode node) {
        if (node == null) return;

        inorder(arr, node.left);
        arr.add(node.val);
        inorder(arr, node.right);
    }
}

Iterative approach

/**
 * author: jooncco
 * written: 2022. 9. 8. Tue. 13:36:14 [UTC+9]
 **/

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> result= new LinkedList<>();

        TreeNode curNode = root;
        while (true) {
            if (curNode == null) {
                if (stack.isEmpty()) break;
                result.add(stack.peek().val);
                curNode= stack.pop().right;
            } else {
                if (curNode.left != null) {
                    stack.push(curNode);
                    curNode= curNode.left;
                } else {
                    result.add(curNode.val);
                    curNode= curNode.right;
                }
            }
        }
        return result;
    }
}

Complexity

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