Preorder Traversal

Easy

Root, then left, then right

Problem

Return the preorder traversal (root, left, right) of a binary tree.

In simple words

Visit the node first, then recurse left, then right (Node-Left-Right).

The idea

Visit the node before descending, so a parent always appears before everything beneath it. That ordering is what makes preorder the right choice for copying a tree or serialising it.

The trick

Root first: the output starts with the root and each subtree's root leads its block.
Preorder plus inorder uniquely reconstructs a tree.

←→stepspaceplay

1/8

Optimal

timeO(n)spaceO(h)

Order = when you emit the node.

1function inorder(node) {2  if (!node) return;3  inorder(node.left);4  visit(node.val);        // node between children5  inorder(node.right);6}

Input

nodes: 6, 5 edges

Output

output: —
inorder: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: tree = [1,null,2,3]
Output:: [1, 2, 3]
Explanation:: Root, then left subtree, then right → 1,2,3.

Example 2

Input:: tree = [1,2,3]
Output:: [1, 2, 3]
Explanation:: Visit 1, then 2, then 3.

Example 3

Input:: tree = []
Output:: []
Explanation:: Empty tree → nothing.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.