94. Binary Tree Inorder Traversal

# Medium, DFS

Solution 1: Recursive

Use help function, return nothing when satisficed stop condition. Pass result list as a parameter. Return result in main function

Java(I)

// Some code
class Solution {
    ArrayList<Integer> res = new ArrayList<Integer>();
    
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null)
            return res;
        
        inorderTraversal(root.left);
        res.add(root.val);
        inorderTraversal(root.right);
        return res;
    }
}

Java(II)

class Solution {
    private void inorder(TreeNode root, ArrayList<Integer> res) {
        // stop condition
        if(root == null) return;
        
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }

    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }
}

Python

    def traversal(self, root, result):
        if root == None:
            return
        
        self.traversal(root.left, result)
        result.append(root.val)
        self.traversal(root.right, result)
        
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        # consider edge case
        result = []
        if root == None:
            return result
        
        # condier regular case
        self.traversal(root, result)
        return result

Compared to preorder traversal, traversal order is changegd to left-root-right in sub-function

Solution 2: Divide & Conquer

Divide and conquer are the same as preorder binary traversal. Combine order is changed to left-root-right. Return result when satisfied stop condition.

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        # consider edge case
        result = []
        if root == None:
            return result
        
        # regular case
        left = self.inorderTraversal(root.left)
        right = self.inorderTraversal(root.right)
        
        result.extend(left)
        result.append(root.val)
        result.extend(right)
        return result

Solution 1 is faster than solution 2.

Solution 3: Iterative (while-loop)

Push all root until left most to the stack, then pop it and add it to res. Switch to the right subtree, then repeat the last steps. It obeys the order left -> root -> right

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack = []
        res = []
        # edge case
        if root == None:
            return res
        
        # regular case
        while root != None or len(stack) != 0:
            while root != None:
                stack.append(root)
                root = root.left
            root = stack.pop()
            res.append(root.val)
            root = root.right
        return res

Java

// Some code
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        while(root != null || !stack.isEmpty()) {
            while(root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
}