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

💡 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