Loading…

easyTreesAsked very often

Tree: Preorder Traversal

Q: How do you solve Tree: Preorder Traversal using the Recursive Preorder — Node, Left, Right approach?

When to use it: Start here. Three lines; just remember the visit comes first. Preorder is defined recursively: to traverse a node, visit it immediately, then fully traverse its left subtree, then its right subtree. **Visit-first is the defining move.** The only difference between the three DFS traversals is where the visit sits among the two recursive calls. Putting it first — before recursing into either child — yields preorder, which always emits the root before anything below it. **Why top-down matters.** Because a parent is always processed before its children, preorder is the order you want when each child's handling depends on the parent already existing: serializing a tree to a string, deep-copying it node by node, or writing an expression tree in prefix (Polish) notation. Reconstructing a tree from a preorder sequence is straightforward precisely because the root comes first. **Base case.** A null pointer (the child of a leaf) has nothing to visit, so it returns and the recursion unwinds. **Not sorted on a BST.** Unlike inorder, preorder on a BST is not sorted — it lists the root, then the entire smaller-than-root subtree, then the larger one. If you need sorted output, that's inorder. Time complexity: O(n). Space complexity: O(h).

Q: How do you solve Tree: Preorder Traversal using the Iterative Preorder — Explicit Stack approach?

When to use it: Offer when recursion is discouraged. The push-right-then-left detail is the part interviewers test. Preorder visits the root first, which maps cleanly onto a stack: pop a node, visit it, and schedule its children for later. **The push order is the whole trick.** A stack is last-in-first-out, so whatever you push *last* is popped *first*. We want the left child handled before the right, so we push the **right child first and the left child second**. On the next iteration the left child is on top and gets popped, visited, and expanded before the right subtree is ever touched. **Why visit on pop.** Unlike inorder, there's no waiting: the moment we pop a node we can emit it, because preorder owes the node before its subtrees. After emitting, we push its children and move on. **Guard against null children.** Only push children that exist; pushing nulls would force an extra null check on pop. The loop ends when the stack is empty, meaning every node has been visited. Time complexity: O(n). Space complexity: O(h).

Trees & BST · 40 of 41 · 8 min

Given a pointer to the root of a binary tree, print the preorder traversal of the tree: the values visited in Node, Left-subtree, Right-subtree order, separated by spaces.

In plain English

Produce the sequence of node values in Node → Left → Right order. We emit a node's value the instant we arrive at it, then descend into its left subtree fully, then its right subtree. The root is always first in the output.

Examples

Example 1

Input: root = [4,2,5,1,3] (4 has children 2,5; 2 has children 1,3)
Output: 4 2 1 3 5
Note: Visit 4, then its left subtree (2, then 1, then 3), then its right subtree (5).

Example 2

Input: root = [1,null,2,3] (1 → right 2; 2 → left 3)
Output: 1 2 3
Note: Visit 1, no left child, go right to 2, visit 2, then its left child 3.

Example 3

Input: root = [1]
Output: 1
Note: Single node — just the node, no subtrees.

Constraints

1 ≤ number of nodes ≤ 500
1 ≤ node value ≤ 500
The tree is non-empty
Output values are space-separated in preorder sequence

Clarifying questions4First question: Should I print the values or return a list?Explore questions

Q1.Should I print the values or return a list?
HackerRank prints space-separated values. Returning a list is cleaner for testing in a general interview — confirm the expected output form.
Q2.Recursive or iterative?
Recursive is the clean default. Offer the stack-based version if the interviewer asks to avoid recursion.
Q3.In the iterative version, which child do I push first?
Push the RIGHT child first, then the left. A stack is LIFO, so the left child (pushed last) is popped and processed first — matching Node, Left, Right.
Q4.Is preorder of a BST sorted?
No. Only inorder yields sorted order on a BST. Preorder is for top-down processing like serialization.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Preorder = visit the Node first, then the Left subtree, then the Right subtree. Recursively it's three lines: visit, recurse left, recurse right. The iterative version uses a stack: push the root, then loop — pop and visit a node, push its RIGHT child first and its LEFT child second, so left is processed before right. Both are O(n) time; O(h) space. Preorder is the natural order for serializing or cloning a tree top-down.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can produce preorder recursively and iteratively, and whether you get the stack push order right (right child before left).

Where candidates slip

In the iterative version, pushing the LEFT child before the right — which reverses the output so right subtrees come first.

How to stand out

Write the recursion instantly, then derive the stack version and explain WHY you push right before left (LIFO means the last pushed is popped first).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Recursive Preorder — Node, Left, Right	`O(n)`	`O(h)`	Start here. Three lines; just remember the visit comes first.	Read
2	Iterative Preorder — Explicit StackOptimal	`O(n)`	`O(h)`	Offer when recursion is discouraged. The push-right-then-left detail is the part interviewers test.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

When is the node visited?

How to read it:Preorder visits the node before either subtree — the top-down DFS.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Recursive Preorder — Node, Left, Right

TimeO(n)SpaceO(h)

Start here. Three lines; just remember the visit comes first.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Preorder means the node is processed before its subtrees. Where does the visit go relative to the two recursive calls?

2Hint 2Explore hint

Base case: a null node produces nothing → return.

3Hint 3Explore hint

For a real node: visit it, then recurse left, then recurse right. The visit is the very first action.

A · Core idea

Preorder is defined recursively: to traverse a node, visit it immediately, then fully traverse its left subtree, then its right subtree.

Visit-first is the defining move. The only difference between the three DFS traversals is where the visit sits among the two recursive calls. Putting it first — before recursing into either child — yields preorder, which always emits the root before anything below it.

Why top-down matters. Because a parent is always processed before its children, preorder is the order you want when each child's handling depends on the parent already existing: serializing a tree to a string, deep-copying it node by node, or writing an expression tree in prefix (Polish) notation. Reconstructing a tree from a preorder sequence is straightforward precisely because the root comes first.

Base case. A null pointer (the child of a leaf) has nothing to visit, so it returns and the recursion unwinds.

Not sorted on a BST. Unlike inorder, preorder on a BST is not sorted — it lists the root, then the entire smaller-than-root subtree, then the larger one. If you need sorted output, that's inorder.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [4,2,5,1,3]

Preorder order on [4,2,5,1,3]

How to read it:Visit order in parentheses: 4 first (root), then 2,1,3,5.

Rendering diagram…

Final result4 2 1 3 5

C · Code with teaching comments

Reference implementation preview// Definition for a binary tree node. class Node { int data; Node left; Node right;Explore the full code

solution.javaJava

Recursive Preorder — Node, Left, Right — reference

4 teaching notes

1
// Definition for a binary tree node.
2
class Node {
3
    int data;
4
    Node left;
5
    Node right;
6
    Node(int data) { this.data = data; }
7
}
8
 
9
public void preorder(Node root) {
10
    if (root == null) return;          // base case: nothing to visit
11
    System.out.print(root.data + " "); // 1) visit the node FIRST
12
    preorder(root.left);               // 2) left subtree
13
    preorder(root.right);              // 3) right subtree
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

Preorder = inorder with the visit moved to the front. All three traversals are the same three statements reordered; preorder puts the visit first, giving you the parent before its descendants.

ComplexityO(n) time, O(h) space — Each node is visited exactly once with O(1) work → O(n) time. Recursion depth equals tree height h → O(h) space (O(log n) balanced, O(n) skewed).

E · Edge cases and pitfalls6root = [1] — Visit 1, both children null → output '1'.Explore edge cases

Edge cases handled

root = [1]Visit 1, both children null → output '1'.
Left-skewed chain 3→2→1Visit each node on the way down → '3 2 1'.
Right-skewed chain 1→2→3Visit then go right repeatedly → '1 2 3'.

Pitfalls

Visiting after recursing left — that's inorder, not preorder.
Forgetting the null base case.
Recursing right before left — swaps the subtree order.

03.2

Approach 2 of 2 · Optimal

Iterative Preorder — Explicit Stack

TimeO(n)SpaceO(h)

Offer when recursion is discouraged. The push-right-then-left detail is the part interviewers test.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Use a stack seeded with the root. What do you do each iteration to emit the root before its children?

2Hint 2Explore hint

Pop a node and visit it immediately (root-first). Then push its children so the LEFT is processed next.

3Hint 3Explore hint

A stack is LIFO: push the RIGHT child first, then the LEFT, so the left pops out before the right.

A · Core idea

Preorder visits the root first, which maps cleanly onto a stack: pop a node, visit it, and schedule its children for later.

The push order is the whole trick. A stack is last-in-first-out, so whatever you push last is popped first. We want the left child handled before the right, so we push the right child first and the left child second. On the next iteration the left child is on top and gets popped, visited, and expanded before the right subtree is ever touched.

Why visit on pop. Unlike inorder, there's no waiting: the moment we pop a node we can emit it, because preorder owes the node before its subtrees. After emitting, we push its children and move on.

Guard against null children. Only push children that exist; pushing nulls would force an extra null check on pop. The loop ends when the stack is empty, meaning every node has been visited.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [4,2,5,1,3]

Stack expansion order

How to read it:Each pop visits a node and pushes right-then-left so left is handled next.

Rendering diagram…

Final result4 2 1 3 5

C · Code with teaching comments

solution.javaJava

Iterative Preorder — Explicit Stack — optimal

4 teaching notes

1
public void preorder(Node root) {
2
    if (root == null) return;
3
    Deque<Node> stack = new ArrayDeque<>();
4
    // Seed the stack with the root so it's visited first.
5
    stack.push(root);
6
    while (!stack.isEmpty()) {
7
        Node node = stack.pop();
8
        System.out.print(node.data + " ");      // visit on pop (root-first)
9
        if (node.right != null) stack.push(node.right); // RIGHT first...
10
        if (node.left != null) stack.push(node.left);   // ...LEFT last → popped first
11
    }
12
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.12 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

LIFO reverses push order, so to get Left-before-Right you push Right-before-Left. Saying that out loud — 'stack is LIFO, so I push the child I want last' — signals you understand the data structure, not just the recipe.

ComplexityO(n) time, O(h) space — Each node is pushed once and popped once → O(n) time. The stack holds at most O(h) nodes (right children waiting along the current path) — up to O(n) for a degenerate tree.

E · Edge cases and pitfalls6root = [1] — Push 1, pop-visit 1, no children → '1'.Explore edge cases

Edge cases handled

root = [1]Push 1, pop-visit 1, no children → '1'.
Left-skewed chain 3→2→1Each pop pushes only a left child → '3 2 1'.
Right-skewed chain 1→2→3Each pop pushes only a right child → '1 2 3'.

Pitfalls

Pushing left before right — reverses subtree order in the output.
Pushing null children — forces an extra null check on every pop.
Visiting on push instead of pop — works for preorder but breaks if you later adapt this skeleton; visit-on-pop is the standard form.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic void preorder(Node root) { if (root == null) return; Deque<Node> stack = new ArrayDeque<>(); stack.push(root); while (!stack.isEmpty()) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong push order in the iterative version

A stack is LIFO. Pushing the left child first means the right child is on top and gets processed before the left — reversing the intended order.

Explore the code comparison

Don't write this

if (node.left != null) stack.push(node.left);
if (node.right != null) stack.push(node.right); // right ends up on top

Write this instead

if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);   // left ends up on top

Visiting after the left recursion (inorder by accident)

Preorder must emit the node before either subtree. Printing after recursing left produces inorder output instead.

Explore the code comparison

Don't write this

def preorder(root):
    if root is None:
        return
    preorder(root.left)
    print(root.data, end=' ')   # too late -> inorder
    preorder(root.right)

Write this instead

def preorder(root):
    if root is None:
        return
    print(root.data, end=' ')   # first -> preorder
    preorder(root.left)
    preorder(root.right)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Depth-first traversal in Node → Left → Right order

Code pattern to memorize

preorder(node):
    if node is null: return
    visit(node)
    preorder(node.left)
    preorder(node.right)

Rules to remember

1Order is Node, Left, Right — the node is visited before either subtree.
2Iterative: push right child first, then left, so the left is popped and processed first.
3Preorder visits the root first, making it ideal for serialization, cloning, and copying top-down.
4The base case (null → return) stops the recursion at the bottom of each branch.
5Preorder of a BST is NOT sorted — only inorder gives sorted order.

Use this pattern when

Serializing or deep-copying a tree (you need the root before its children)
Building a prefix/Polish-notation representation of an expression tree
Any traversal where the parent must be processed before its descendants

Choose another pattern when

You need sorted BST output → inorder, not preorder
You need children-before-parent (freeing nodes, postfix expressions) → postorder
You need level-by-level output → BFS level order

Interview takeaway

Preorder is the 'top-down' DFS: process a node, then its subtrees. The recursion is just the inorder code with the visit moved to the front. The iterative version's push-right-then-left ordering is the detail interviewers probe.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternPreorder DFS (Node → Left → Right). One of three traversals differing only in visit position; preorder is top-down, emitting the root before its subtrees, which makes it the order for serialization and reconstruction. The iterative stack version hinges on pushing the right child before the left.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Tree: Inorder Traversal
Move the visit BETWEEN the two recursions (Left, Node, Right); sorted on a BST.
Tree: Postorder Traversal
Move the visit AFTER both recursions (Left, Right, Node).
Serialize and Deserialize Binary Tree
Coming soon
Preorder with null markers makes serialization and rebuilding straightforward.
Construct Binary Tree from Preorder and Inorder
The first preorder element is always the root — that's why preorder is so useful for reconstruction.

Same pattern

←

Tree: Postorder Traversal

Continue · Next problem

Swap Nodes [Algo]

easyTreesAsked very often

Tree: Preorder Traversal

Trees & BST · 40 of 41 · 8 min

Given a pointer to the root of a binary tree, print the preorder traversal of the tree: the values visited in Node, Left-subtree, Right-subtree order, separated by spaces.

In plain English

Examples

Example 1

Input: root = [4,2,5,1,3] (4 has children 2,5; 2 has children 1,3)
Output: 4 2 1 3 5
Note: Visit 4, then its left subtree (2, then 1, then 3), then its right subtree (5).

Example 2

Input: root = [1,null,2,3] (1 → right 2; 2 → left 3)
Output: 1 2 3
Note: Visit 1, no left child, go right to 2, visit 2, then its left child 3.

Example 3

Input: root = [1]
Output: 1
Note: Single node — just the node, no subtrees.

Constraints

1 ≤ number of nodes ≤ 500
1 ≤ node value ≤ 500
The tree is non-empty
Output values are space-separated in preorder sequence

Clarifying questions4First question: Should I print the values or return a list?Explore questions

Q1.Should I print the values or return a list?
HackerRank prints space-separated values. Returning a list is cleaner for testing in a general interview — confirm the expected output form.
Q2.Recursive or iterative?
Recursive is the clean default. Offer the stack-based version if the interviewer asks to avoid recursion.
Q3.In the iterative version, which child do I push first?
Push the RIGHT child first, then the left. A stack is LIFO, so the left child (pushed last) is popped and processed first — matching Node, Left, Right.
Q4.Is preorder of a BST sorted?
No. Only inorder yields sorted order on a BST. Preorder is for top-down processing like serialization.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can produce preorder recursively and iteratively, and whether you get the stack push order right (right child before left).

Where candidates slip

In the iterative version, pushing the LEFT child before the right — which reverses the output so right subtrees come first.

How to stand out

Write the recursion instantly, then derive the stack version and explain WHY you push right before left (LIFO means the last pushed is popped first).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Recursive Preorder — Node, Left, Right	`O(n)`	`O(h)`	Start here. Three lines; just remember the visit comes first.	Read
2	Iterative Preorder — Explicit StackOptimal	`O(n)`	`O(h)`	Offer when recursion is discouraged. The push-right-then-left detail is the part interviewers test.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

When is the node visited?

How to read it:Preorder visits the node before either subtree — the top-down DFS.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Recursive Preorder — Node, Left, Right

TimeO(n)SpaceO(h)

Start here. Three lines; just remember the visit comes first.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Preorder means the node is processed before its subtrees. Where does the visit go relative to the two recursive calls?

2Hint 2Explore hint

Base case: a null node produces nothing → return.

3Hint 3Explore hint

For a real node: visit it, then recurse left, then recurse right. The visit is the very first action.

A · Core idea

Preorder is defined recursively: to traverse a node, visit it immediately, then fully traverse its left subtree, then its right subtree.

Base case. A null pointer (the child of a leaf) has nothing to visit, so it returns and the recursion unwinds.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [4,2,5,1,3]

Preorder order on [4,2,5,1,3]

How to read it:Visit order in parentheses: 4 first (root), then 2,1,3,5.

Rendering diagram…

Final result4 2 1 3 5

C · Code with teaching comments

Reference implementation preview// Definition for a binary tree node. class Node { int data; Node left; Node right;Explore the full code

solution.javaJava

Recursive Preorder — Node, Left, Right — reference

4 teaching notes

1
// Definition for a binary tree node.
2
class Node {
3
    int data;
4
    Node left;
5
    Node right;
6
    Node(int data) { this.data = data; }
7
}
8
 
9
public void preorder(Node root) {
10
    if (root == null) return;          // base case: nothing to visit
11
    System.out.print(root.data + " "); // 1) visit the node FIRST
12
    preorder(root.left);               // 2) left subtree
13
    preorder(root.right);              // 3) right subtree
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

Preorder = inorder with the visit moved to the front. All three traversals are the same three statements reordered; preorder puts the visit first, giving you the parent before its descendants.

ComplexityO(n) time, O(h) space — Each node is visited exactly once with O(1) work → O(n) time. Recursion depth equals tree height h → O(h) space (O(log n) balanced, O(n) skewed).

E · Edge cases and pitfalls6root = [1] — Visit 1, both children null → output '1'.Explore edge cases

Edge cases handled

root = [1]Visit 1, both children null → output '1'.
Left-skewed chain 3→2→1Visit each node on the way down → '3 2 1'.
Right-skewed chain 1→2→3Visit then go right repeatedly → '1 2 3'.

Pitfalls

Visiting after recursing left — that's inorder, not preorder.
Forgetting the null base case.
Recursing right before left — swaps the subtree order.

03.2

Approach 2 of 2 · Optimal

Iterative Preorder — Explicit Stack

TimeO(n)SpaceO(h)

Offer when recursion is discouraged. The push-right-then-left detail is the part interviewers test.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Use a stack seeded with the root. What do you do each iteration to emit the root before its children?

2Hint 2Explore hint

Pop a node and visit it immediately (root-first). Then push its children so the LEFT is processed next.

3Hint 3Explore hint

A stack is LIFO: push the RIGHT child first, then the LEFT, so the left pops out before the right.

A · Core idea

Preorder visits the root first, which maps cleanly onto a stack: pop a node, visit it, and schedule its children for later.

Guard against null children. Only push children that exist; pushing nulls would force an extra null check on pop. The loop ends when the stack is empty, meaning every node has been visited.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [4,2,5,1,3]

Stack expansion order

How to read it:Each pop visits a node and pushes right-then-left so left is handled next.

Rendering diagram…

Final result4 2 1 3 5

C · Code with teaching comments

solution.javaJava

Iterative Preorder — Explicit Stack — optimal

4 teaching notes

1
public void preorder(Node root) {
2
    if (root == null) return;
3
    Deque<Node> stack = new ArrayDeque<>();
4
    // Seed the stack with the root so it's visited first.
5
    stack.push(root);
6
    while (!stack.isEmpty()) {
7
        Node node = stack.pop();
8
        System.out.print(node.data + " ");      // visit on pop (root-first)
9
        if (node.right != null) stack.push(node.right); // RIGHT first...
10
        if (node.left != null) stack.push(node.left);   // ...LEFT last → popped first
11
    }
12
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.12 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6root = [1] — Push 1, pop-visit 1, no children → '1'.Explore edge cases

Edge cases handled

root = [1]Push 1, pop-visit 1, no children → '1'.
Left-skewed chain 3→2→1Each pop pushes only a left child → '3 2 1'.
Right-skewed chain 1→2→3Each pop pushes only a right child → '1 2 3'.

Pitfalls

Pushing left before right — reverses subtree order in the output.
Pushing null children — forces an extra null check on every pop.
Visiting on push instead of pop — works for preorder but breaks if you later adapt this skeleton; visit-on-pop is the standard form.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic void preorder(Node root) { if (root == null) return; Deque<Node> stack = new ArrayDeque<>(); stack.push(root); while (!stack.isEmpty()) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong push order in the iterative version

A stack is LIFO. Pushing the left child first means the right child is on top and gets processed before the left — reversing the intended order.

Explore the code comparison

Don't write this

if (node.left != null) stack.push(node.left);
if (node.right != null) stack.push(node.right); // right ends up on top

Write this instead

if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);   // left ends up on top

Visiting after the left recursion (inorder by accident)

Preorder must emit the node before either subtree. Printing after recursing left produces inorder output instead.

Explore the code comparison

Don't write this

def preorder(root):
    if root is None:
        return
    preorder(root.left)
    print(root.data, end=' ')   # too late -> inorder
    preorder(root.right)

Write this instead

def preorder(root):
    if root is None:
        return
    print(root.data, end=' ')   # first -> preorder
    preorder(root.left)
    preorder(root.right)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Depth-first traversal in Node → Left → Right order

Code pattern to memorize

preorder(node):
    if node is null: return
    visit(node)
    preorder(node.left)
    preorder(node.right)

Rules to remember

1Order is Node, Left, Right — the node is visited before either subtree.
2Iterative: push right child first, then left, so the left is popped and processed first.
3Preorder visits the root first, making it ideal for serialization, cloning, and copying top-down.
4The base case (null → return) stops the recursion at the bottom of each branch.
5Preorder of a BST is NOT sorted — only inorder gives sorted order.

Use this pattern when

Serializing or deep-copying a tree (you need the root before its children)
Building a prefix/Polish-notation representation of an expression tree
Any traversal where the parent must be processed before its descendants

Choose another pattern when

You need sorted BST output → inorder, not preorder
You need children-before-parent (freeing nodes, postfix expressions) → postorder
You need level-by-level output → BFS level order

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Tree: Inorder Traversal
Move the visit BETWEEN the two recursions (Left, Node, Right); sorted on a BST.
Tree: Postorder Traversal
Move the visit AFTER both recursions (Left, Right, Node).
Serialize and Deserialize Binary Tree
Coming soon
Preorder with null markers makes serialization and rebuilding straightforward.
Construct Binary Tree from Preorder and Inorder
The first preorder element is always the root — that's why preorder is so useful for reconstruction.

Same pattern

←

Tree: Postorder Traversal

Continue · Next problem

Swap Nodes [Algo]