easy +10 pts

Tree inorder generator

Implement a generator that yields a binary tree's values in inorder traversal.

Implement a generator function `inorder(root)` that takes the root node of a binary tree and yields the integer values of the tree's nodes in **inorder** traversal (left subtree, current node, right subtree). Each node is an object with attributes `val` (integer), `left` (either a node or `None`), and `right` (either a node or `None`). For example, a node can be created with `type('Node', (), {"val": 1, "left": None, "right": None})` or using a simple class. Your function must be a generator: it must contain at least one `yield` and must not return a list. The tree is not necessarily balanced. The total number of nodes can be up to 10^5, so your solution must not use recursion (which would exceed recursion limits) and must use constant extra space beyond the generator's own stack (O(h) space where h is tree height).

Constraints

- Node values are integers. - The tree has between 0 and 100,000 nodes. - The tree is not necessarily balanced. - Expected time complexity: O(n), where n is the number of nodes. - Expected space complexity: O(h), where h is the height of the tree.

Example

>>> class Node:
...     def __init__(self, val=0, left=None, right=None):
...         self.val = val
...         self.left = left
...         self.right = right
>>> root = Node(1, None, Node(2, Node(3)))
>>> list(inorder(root))
[1, 3, 2]
>>> list(inorder(None))
[]
10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use an explicit stack to simulate the recursive traversal.
Push nodes and their 'state' or use the classic pattern: go left as far as possible, then yield and go right.
Remember that `None` nodes should simply produce no values.
Python 3
All tests passed!
Test Results
Press Ctrl+Enter or click Run Tests to execute your code.