Inorder Traversal

Difficulty: Easy · Topic: Traversals

The tree is given as a level-order array where None marks a missing child. A build_tree(arr) helper (and TreeNode) is provided. Return the in-order traversal: left subtree, then the node, then the right subtree.

Examples

inorder([1,null,2,3])
→ [1,3,2]

1 has only a right child (2), whose left child is 3.

inorder([4,2,6,1,3,5,7])
→ [1,2,3,4,5,6,7]

A balanced BST → sorted output.

Target complexity: time O(n), space O(n)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.