0094. Inorder Traversal

Easy | Tree + Traversal | 20 ms (99.17%), 13.9 MB (98.55%)

❓ Problem Statement

Source: LeetCode - Binary Tree Inorder Traversal GitHub: Solution / Performance

Given the root of a binary tree, return the inorder traversal of its nodes' values.

✍🏻 Constraints & Example

Constraints:

• The number of nodes in the tree is in the range [0, 100].

• -100 <= Node.val <= 100

💡 Ideas

Inorder traversal stops iterating when there is no left-child node.

In other words, we need to keep non-visited nodes along the path.

Pop the stack to retrieve the tuple/pair with the current node and visited status.

• If already being visited, we could append the node's value to the answer.

• If not:

  • First, push the right-child node with non-visited status (if the node exists)

  • Second, push the current node but with visited status

  • Last, push the left-child node with non-visited status (if the node exists)

🤖 Python3

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        # (base case)
        if not root: return []
        if not root.left and not root.right: return [root.val]
        
        # ==================================================
        #  Binary Tree + In-order Traversal               =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        ret = []
        stack = [(root, False)]
        
        while stack:
            node, visited = stack.pop()
            
            if visited:
                ret.append(node.val)
                
            else:
                if node.right: stack.append((node.right, False))
                stack.append((node, True))
                if node.left: stack.append((node.left, False))
            
        return ret

        '''
        # ==================================================
        #  Binary Tree + In-order Traversal               =
        # ==================================================
        # time  : O(n)
        # space : O(n)

        return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
        '''

🤖 Java

class Solution {
    /**
     * @time  : O(n)
     * @space : O(n)
     */

    public List<Integer> inorderTraversal(TreeNode root) {
        /* base case */
        if(root == null) return new ArrayList<>();
        
        List<Integer> result = new ArrayList<>();
        Stack<Pair<TreeNode, Boolean>> stack = new Stack<Pair<TreeNode, Boolean>>();
        stack.push(new Pair<TreeNode, Boolean>(root, false));
        
        while(!stack.isEmpty()) {
            Pair<TreeNode, Boolean> object = stack.pop();
            TreeNode node = object.getKey();
            Boolean visited = object.getValue();
            
            if(visited == true) result.add(node.val);
            else {
                if(node.right != null) stack.push(new Pair<TreeNode, Boolean>(node.right, false));
                stack.push(new Pair<TreeNode, Boolean>(node, true));
                if(node.left != null) stack.push(new Pair<TreeNode, Boolean>(node.left, false));
            }
        }
        
        return result;
    }
}