Inorder traversal
You get the root of a binary tree. Each node has a value val and up to two children, left and right. A node's subtree is the node together with everything below it.
Return a list of all the values in inorder: for every node, first the values of its left subtree, then its own value, then the values of its right subtree. An empty tree (root is None) gives an empty list. Leave the tree itself unchanged.
Examples write a tree level by level, left to right, with None where a child is missing.
root = [2, 1, 3]Output[1, 2, 3]The left child 1 comes before the root 2, and the right child 3 comes after it.
root = [5, 8, 1, None, 4]Output[8, 4, 5, 1]The left subtree of 5 is 8 with a right child 4, which gives 8, 4. Then comes 5, then its right subtree, 1. The order follows positions in the tree, not the size of the values.
root = []Output[]An empty tree has no values.
0 ≤ number of nodes ≤ 100
-100 ≤ val ≤ 100
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.