Binary Tree Inorder Traversal

Return the inorder traversal of a binary tree as a list of node values.

binary-tree traversal recursion

Write a function `inorder_traversal(root)` that performs an inorder traversal of a binary tree and returns a list of the node values in the order they are visited (left subtree, then root, then right subtree).

Each node is represented as a dictionary with keys `"val"`, `"left"`, and `"right"`. The `"left"` and `"right"` values are either dictionaries or `None` (for an empty tree, `root` is `None`).

For example, the tree `1 -> right 2 -> left 3` is represented as:
```python
{"val": 1, "left": None, "right": {"val": 2, "left": {"val": 3, "left": None, "right": None}, "right": None}}
```

In an inorder traversal, visit the left subtree, then the current node, then the right subtree. If the tree is empty (`root is None`), return an empty list.

Constraints

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

Example

```python
# Example 1:
# Tree:   1
#          \
#           2
#          /
#         3
root = {"val": 1, "left": None, "right": {"val": 2, "left": {"val": 3, "left": None, "right": None}, "right": None}}
print(inorder_traversal(root))  # Output: [1, 3, 2]

# Example 2:
root = None
print(inorder_traversal(root))  # Output: []
```

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think recursively: left subtree, current node, right subtree.

Base case: if root is None, return an empty list.

Access node values with root['val'] and children with root['left'] and root['right'].

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.