Preorder traversal
Visit the root first, then everything in the left subtree, then everything in the right subtree. About 8 minutes.
Root, then left, then right
Preorder of a tree means: write down the value at the top first, then do preorder on the left subtree, then on the right subtree, joining the results in that order.
An empty tree adds nothing, so the base case is an empty list. Because the function calls itself on smaller trees, the whole thing is only a few lines.
if not root:
return []
out = [root.val]
out += preorder_traversal(root.left)
out += preorder_traversal(root.right)
return out- result
- [1]
Visit the root before anything else.
Tracing it on a small tree
Take a tree with 1 at the top, 2 as its left child and 3 as its right child. Preorder writes down 1 first, then dives into the left subtree and writes 2, then comes back up and does the right subtree, 3. The result is 1, 2, 3.
Notice it follows the shape of the tree, not the size of the numbers.
For the tree with root 5, left child 3, and right child 8, what does preorder traversal return?
- A[5, 3, 8]
- B[3, 5, 8]
- C[3, 8, 5]
Show the answer
[5, 3, 8]. Root 5 is visited first, then the left subtree (3), then the right subtree (8).
Preorder traversal
Given the root of a binary tree, return the values of its nodes visited in preorder: the current node first, then every node in its left subtree, then every node in its right subtree. If the tree is empty, return an empty list.
root = [1, 2, 3] → [1, 2, 3]
0 ≤ number of nodes ≤ 10,000 · -1,000,000 ≤ node.val ≤ 1,000,000