Code it · Write it
Write an inorder traversal
Write inorder(root) (Python, JavaScript and TypeScript). root is a TreeNode with val, left and right (None/null where there is no child), or None/null for an empty tree.
Return a list (an array in JavaScript) of the values in inorder: everything in the left subtree, then the node itself, then everything in the right subtree. For a binary search tree that is sorted order.
A recursive helper is the natural fit: for a node, handle its left subtree, record its value, then handle its right subtree. An empty subtree has nothing to add.
def inorder(root):
# Return the values: left subtree, then the node, then the right subtree.
out = []
return out