algoadvance

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

In an inorder traversal, for each node:

1. Visit the left subtree.
2. Visit the node itself.
3. Visit the right subtree.

Example:

Input: root = [1, null, 2, 3]
Output: [1, 3, 2]

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Clarifying Questions:

1. Q: Should I consider any edge cases specifically, such as an empty tree?
   • A: Yes, handle an empty tree by returning an empty list.
2. Q: Can the tree have duplicate values?
   • A: Yes, the nodes can contain duplicate values.
3. Q: Will the tree always be a valid binary tree?
   • A: Yes, you can assume the input will always represent a valid binary tree.

Strategy:

We can solve this problem iteratively or recursively. Here, we’ll show both methods.

Recursive Approach:

1. Define a helper function to perform the inorder traversal.
2. Traverse the left subtree, append the node’s value, then traverse the right subtree.
3. Use the base case of an empty node to terminate the recursion.

Iterative Approach:

1. Use a stack to simulate the call stack of the recursive approach.
2. Push nodes onto the stack as we traverse to the left.
3. When reaching a null node, pop from the stack, visit the node, and traverse its right subtree.

Code:

Recursive Approach:

from typing import Optional, List

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorderTraversal(root: Optional[TreeNode]) -> List[int]:
    def helper(node: Optional[TreeNode], result: List[int]):
        if not node:
            return
        helper(node.left, result)
        result.append(node.val)
        helper(node.right, result)
    
    result = []
    helper(root, result)
    return result

Iterative Approach:

def inorderTraversal(root: Optional[TreeNode]) -> List[int]:
    result, stack = [], []
    current = root
    
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
    
    return result

Time Complexity:

Both the recursive and iterative methods have the same time complexity.

• Time Complexity: O(n) where n is the number of nodes in the binary tree. This is because each node is visited exactly once.
• Space Complexity: O(n) in the worst case for both methods due to the space needed for the recursion stack or the iterative stack when the tree is completely unbalanced.

Both methods will perform efficiently within the given constraints.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?