Easy L -> Visit -> R Trees
In plain English: Visit every node in a binary tree in left-root-right order (gives sorted order for BSTs).
Inorder visits left before root before right — for BSTs this produces sorted output because left < root < right at every node.
Prompt
Return the inorder traversal of a binary tree as a list.
Try to write it from scratch before scrolling down.
Solution
def inorder(node, result=None):
# left, visit, right = sorted for BST
if result is None:
result = []
if node:
inorder(node.left, result)
result.append(node.val)
inorder(node.right, result)
return result
# BST [4,2,6,1,3] inorder => [1,2,3,4,6]