Tree Traversals

Easy

Inorder · Preorder · Postorder

In simple words

Visit a tree's nodes in a set order — left, node, right — like reading branches in a plan.

The idea

The three depth-first orders differ only in when you visit the node relative to its children: preorder (node, left, right), inorder (left, node, right — sorted for a BST), postorder (left, right, node).

The trick

Inorder of a BST yields values in sorted order.

←→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.