Loading…

mediumTreesSometimes asked

Swap Nodes [Algo]

Q: How do you solve Swap Nodes [Algo] using the Build + Recursive Depth-Swap + Inorder (Canonical) approach?

When to use it: The standard, clean solution. Lead with it; it cleanly separates the three concerns. The problem decomposes into three independent pieces; solving each cleanly is what makes it manageable. **1. Build the tree (once).** The input is a flat index list, not a pointer tree, so reconstruct it. Create node objects for ids `1..n` and store them so id `i` maps to `nodes[i]`. Then for each node `i`, read its row `(L, R)`: if `L != -1`, set `nodes[i].left = nodes[L]`; same for the right. Node 1 is the root at depth 1. Getting the 1-based mapping right — array index `i−1` holds node `i`'s children — is the most error-prone step. **2. Swap by depth (per query).** For query `k`, traverse from the root carrying the current depth (root = 1). At every node, if `depth % k == 0`, swap its two child *links* (exchange the pointers; values don't move). Then recurse into both children at `depth + 1`. This touches depths `k, 2k, 3k, …` exactly. Swapping a node with a missing child simply swaps in a null — harmless. **3. Inorder after each query.** Once the swaps for query `k` are applied, run a standard Left-Node-Right inorder to read the current tree and store that as this query's answer. **The cumulative gotcha.** Do *not* rebuild or undo between queries. Query 2 swaps on top of query 1's result. That's why we keep a single mutable tree and keep applying swaps — the second example (k=1 then k=1 flips then un-flips the root) only makes sense under cumulative semantics. Time complexity: O(n·q). Space complexity: O(n).

Q: How do you solve Swap Nodes [Algo] using the Build + BFS Depth Buckets + Iterative Inorder approach?

When to use it: Offer if recursion depth is a worry (skewed tree up to ~1024 deep) or to show an explicit, stack-free traversal. Same three phases, but with two robustness tweaks that matter when the tree is deep. **Bucket nodes by depth.** After building, run a BFS from the root tracking depth, pushing each node into `buckets[depth]`. This precomputes, once, which nodes live at each depth. **Swap via buckets.** For a query `k`, you no longer need to walk the whole tree to find qualifying nodes — just iterate depths `k, 2k, 3k, …` and swap the child links of every node in those buckets. For small `k` this is still O(n) (k=1 hits every node), but it avoids the per-node modulo test and the recursion. The buckets stay valid across queries because swapping children never changes any node's depth. **Iterative inorder.** A skewed input tree can be ~1024 nodes deep. Recursive inorder is usually fine at that depth, but the explicit-stack version (push the left spine, pop-visit, go right) removes any call-stack risk and is a good habit to demonstrate. **Still cumulative.** As before, the single tree is mutated in place across queries; bucketing is just a faster way to locate the nodes to swap. Time complexity: O(n·q). Space complexity: O(n).

Trees & BST · 41 of 41 · 11 min

A binary tree is described by an array indexes where the i-th row (1-indexed) gives the indices of node i's left and right children; a value of -1 means no child. Node 1 is the root and sits at depth 1.

For each query value k, swap the left and right subtrees of every node whose depth is a multiple of k (i.e. depths k, 2k, 3k, …). After performing a query's swaps, record the inorder traversal of the tree. Swaps from earlier queries persist into later ones.

Return the list of inorder traversals, one per query.

In plain English

First reconstruct the actual tree from the flat index list (map 1-based node ids to node objects and wire children, treating −1 as null). Then each query is a depth-conditioned mutation: traverse the tree and, at any node whose depth divides evenly by k, exchange its two child links. Because swaps carry over, you keep mutating the same tree and read its inorder after each query.

Examples

Example 1

Input: indexes = [[2,3],[-1,4],[5,-1],[-1,-1],[-1,-1]], queries = [2]
Output: 4 2 1 3 5
Note: Tree: 1→(2,3); 2→right 4; 3→left 5. Depth-2 nodes are 2 and 3. Swap them: node 2 now has left 4, node 3 now has right 5. Inorder = 4 2 1 3 5.

Example 2

Input: indexes = [[2,3],[-1,-1],[-1,-1]], queries = [1,1]
Output: 3 1 2 / 2 1 3
Note: k=1 swaps every depth. After the first query the root's children flip to (3,2) → inorder 3 1 2. The second k=1 flips them back → 2 1 3. Cumulative.

Example 3

Input: indexes = [[2,3],[-1,-1],[-1,-1]], queries = [2]
Output: 2 1 3
Note: Only depth-2 nodes (2,3) qualify, and they're leaves with nothing to swap, so the tree is unchanged. Inorder 2 1 3.

Constraints

1 ≤ n ≤ 1024 (number of nodes)
1 ≤ number of queries ≤ 1024
1 ≤ k ≤ n for each query
Node values are the node indices 1..n; the root is node 1 at depth 1
Swaps are cumulative across queries

Clarifying questions4First question: Is the index array 0-based or 1-based?Explore questions

Q1.Is the index array 0-based or 1-based?
Node ids are 1-based and the root is node 1 at depth 1. Row i of the array describes node i's children, so array index i−1 holds node i's row. Getting this mapping right is essential.
Q2.Do swaps reset between queries?
No — they are cumulative. Each query swaps on top of all previous swaps, so you mutate one persistent tree rather than rebuilding.
Q3.What depth is the root, and how is 'multiple of k' tested?
Root depth is 1. A node at depth d is swapped when d % k == 0, covering depths k, 2k, 3k, and so on.
Q4.What does −1 mean in a child slot?
No child there — wire it as null. Swapping a node with one or zero children just moves the existing/absent links, which is harmless.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Build a binary tree from the 1-indexed child-index array (row i lists node i's left and right children; −1 = no child; node 1 is the root at depth 1). For each query k, swap the left and right children of every node whose depth is a multiple of k (depths k, 2k, 3k, …), then record the inorder traversal. The crucial detail: swaps are CUMULATIVE — keep mutating one tree across queries, never rebuild. Build is O(n); each query is O(n) to swap by depth plus O(n) for inorder, so total O(n·q).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can build a tree from an index list with correct 1-based indexing, apply a depth-conditioned mutation (swap where depth % k == 0), and produce an inorder traversal — while remembering swaps accumulate across queries.

Where candidates slip

Rebuilding/resetting the tree between queries (treating each independently), off-by-one in depth (root at depth 0 vs 1), or mis-mapping the 1-based index array to node objects.

How to stand out

Separate the three concerns cleanly — build once, swap-by-depth per query, inorder per query — and explicitly note swaps are cumulative so you mutate a single shared tree; mention iterative inorder for deep skewed trees.

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	Build + Recursive Depth-Swap + Inorder (Canonical)	`O(n·q)`	`O(n)`	The standard, clean solution. Lead with it; it cleanly separates the three concerns.	Read
2	Build + BFS Depth Buckets + Iterative InorderOptimal	`O(n·q)`	`O(n)`	Offer if recursion depth is a worry (skewed tree up to ~1024 deep) or to show an explicit, stack-free traversal.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewindex arrayfor each query kYesNoExplore the full tree

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

Build + Recursive Depth-Swap + Inorder (Canonical)

TimeO(n·q)SpaceO(n)

The standard, clean solution. Lead with it; it cleanly separates the three concerns.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

First materialize the tree: create n node objects (1-based) and wire each node's children from its row, treating −1 as null. The root is node 1.

2Hint 2Explore hint

For a query k, recurse from the root tracking depth (starting at 1). At any node where depth % k == 0, swap its left and right child pointers.

3Hint 3Explore hint

After the swap pass, run a normal inorder traversal to collect the values. Do NOT rebuild between queries — swaps accumulate.

A · Core idea

The problem decomposes into three independent pieces; solving each cleanly is what makes it manageable.

1. Build the tree (once). The input is a flat index list, not a pointer tree, so reconstruct it. Create node objects for ids 1..n and store them so id i maps to nodes[i]. Then for each node i, read its row (L, R): if L != -1, set nodes[i].left = nodes[L]; same for the right. Node 1 is the root at depth 1. Getting the 1-based mapping right — array index i−1 holds node i's children — is the most error-prone step.

2. Swap by depth (per query). For query k, traverse from the root carrying the current depth (root = 1). At every node, if depth % k == 0, swap its two child links (exchange the pointers; values don't move). Then recurse into both children at depth + 1. This touches depths k, 2k, 3k, … exactly. Swapping a node with a missing child simply swaps in a null — harmless.

3. Inorder after each query. Once the swaps for query k are applied, run a standard Left-Node-Right inorder to read the current tree and store that as this query's answer.

The cumulative gotcha. Do not rebuild or undo between queries. Query 2 swaps on top of query 1's result. That's why we keep a single mutable tree and keep applying swaps — the second example (k=1 then k=1 flips then un-flips the root) only makes sense under cumulative semantics.

B · Visual dry run

Interactive dry run

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

indexes = [[2,3],[-1,4],[5,-1],[-1,-1],[-1,-1]], queries = [2]

Before and after k=2 swap

How to read it:Depth-2 nodes 2 and 3 swap children; inorder becomes 4 2 1 3 5.

Rendering diagram…

Final result4 2 1 3 5

C · Code with teaching comments

Reference implementation previewimport java.util.*; class Node { int val; Node left;Explore the full code

solution.javaJava

Build + Recursive Depth-Swap + Inorder (Canonical) — reference

5 teaching notes

1
import java.util.*;
2
 
3
class Node {
4
    int val;
5
    Node left;
6
    Node right;
7
    Node(int val) { this.val = val; }
8
}
9
 
10
public int[][] swapNodes(int[][] indexes, int[] queries) {
11
    int n = indexes.length;
12
    // Size n+1 so we can index 1-based (nodes[1]..nodes[n]); nodes[0] stays unused.
13
    Node[] nodes = new Node[n + 1];           // 1-based: nodes[i] is node i
14
    for (int i = 1; i <= n; i++) nodes[i] = new Node(i);
15
    for (int i = 1; i <= n; i++) {
16
        // Row i−1 of the array holds node i's children — the 1-based-to-0-based bridge.
17
        int l = indexes[i - 1][0];            // row i-1 describes node i
18
        int r = indexes[i - 1][1];
19
        // −1 means no child; otherwise link to the already-created node object.
20
        if (l != -1) nodes[i].left = nodes[l];
21
        if (r != -1) nodes[i].right = nodes[r];
22
    }
23
    Node root = nodes[1];                     // root is node 1, depth 1
24
 
25
    int[][] result = new int[queries.length][];
26
    for (int q = 0; q < queries.length; q++) {
27
        // Mutate the SAME tree each query — swaps are cumulative.
28
        swapAtDepth(root, 1, queries[q]);     // cumulative mutation
29
        List<Integer> out = new ArrayList<>();
30
        inorder(root, out);
31
        result[q] = out.stream().mapToInt(Integer::intValue).toArray();
32
    }
33
    return result;
34
}
35
 
36
private void swapAtDepth(Node node, int depth, int k) {
37
    if (node == null) return;
38
    // Swap only at depths that are multiples of k (k, 2k, 3k, …).
39
    if (depth % k == 0) {                     // swap child LINKS
40
        Node tmp = node.left;
41
        node.left = node.right;
42
        node.right = tmp;
43
    }
44
    swapAtDepth(node.left, depth + 1, k);
45
    swapAtDepth(node.right, depth + 1, k);
46
}
47
 
48
private void inorder(Node node, List<Integer> out) {
49
    if (node == null) return;
50
    inorder(node.left, out);
51
    out.add(node.val);
52
    inorder(node.right, out);
53
}

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

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

Treat construction, mutation, and reporting as three separate functions. The only cross-cutting subtlety is that the mutation persists — one tree, repeatedly mutated — which is exactly what the 'swap then un-swap with two k=1 queries' example is testing.

ComplexityO(n·q) time, O(n) space — Building wires n nodes in O(n). Each query visits all n nodes for the swap pass and all n for inorder → O(n) per query, O(n·q) over q queries. Space is O(n) for the nodes plus O(h) recursion ≤ O(n).

E · Edge cases and pitfalls6k larger than the tree's depth — No node satisfies depth % k == 0 → tree unchanged, inorder is the original.Explore edge cases

Edge cases handled

k larger than the tree's depthNo node satisfies depth % k == 0 → tree unchanged, inorder is the original.
Two consecutive k=1 queriesEvery depth swaps then swaps back → second inorder equals the original.
Node with one child swappedThe existing child moves to the other side; the null moves too — still valid.

Pitfalls

Rebuilding or resetting the tree between queries — breaks the cumulative semantics.
Off-by-one on depth: root must be depth 1, so depth % k uses 1-based depth.
Mis-mapping the 1-based index array (using indexes[i] for node i instead of indexes[i−1]).

03.2

Approach 2 of 2 · Optimal

Build + BFS Depth Buckets + Iterative Inorder

TimeO(n·q)SpaceO(n)

Offer if recursion depth is a worry (skewed tree up to ~1024 deep) or to show an explicit, stack-free traversal.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Run one BFS after building to group nodes by depth into buckets.

2Hint 2Explore hint

For a query k, iterate only the buckets at depths k, 2k, 3k, … and swap those nodes' children directly — no full DFS needed.

3Hint 3Explore hint

Use an explicit-stack iterative inorder so a deep, skewed tree can't overflow the call stack.

A · Core idea

Same three phases, but with two robustness tweaks that matter when the tree is deep.

Bucket nodes by depth. After building, run a BFS from the root tracking depth, pushing each node into buckets[depth]. This precomputes, once, which nodes live at each depth.

Swap via buckets. For a query k, you no longer need to walk the whole tree to find qualifying nodes — just iterate depths k, 2k, 3k, … and swap the child links of every node in those buckets. For small k this is still O(n) (k=1 hits every node), but it avoids the per-node modulo test and the recursion. The buckets stay valid across queries because swapping children never changes any node's depth.

Iterative inorder. A skewed input tree can be ~1024 nodes deep. Recursive inorder is usually fine at that depth, but the explicit-stack version (push the left spine, pop-visit, go right) removes any call-stack risk and is a good habit to demonstrate.

Still cumulative. As before, the single tree is mutated in place across queries; bucketing is just a faster way to locate the nodes to swap.

B · Visual dry run

Interactive dry run

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

indexes = [[2,3],[-1,4],[5,-1],[-1,-1],[-1,-1]], queries = [2]

Interactive diagram

Depth buckets

bucket

Active call / nodeSupporting contextReturned stateNot active

Nodes grouped by depth once; query k swaps buckets at k, 2k, 3k…

Final result4 2 1 3 5

C · Code with teaching comments

solution.javaJava

Build + BFS Depth Buckets + Iterative Inorder — optimal

4 teaching notes

1
import java.util.*;
2
 
3
public int[][] swapNodes(int[][] indexes, int[] queries) {
4
    int n = indexes.length;
5
    Node[] nodes = new Node[n + 1];
6
    for (int i = 1; i <= n; i++) nodes[i] = new Node(i);
7
    for (int i = 1; i <= n; i++) {
8
        if (indexes[i - 1][0] != -1) nodes[i].left = nodes[indexes[i - 1][0]];
9
        if (indexes[i - 1][1] != -1) nodes[i].right = nodes[indexes[i - 1][1]];
10
    }
11
    Node root = nodes[1];
12
 
13
    // BFS: bucket nodes by depth (depth never changes under swaps)
14
    Map<Integer, List<Node>> buckets = new HashMap<>();
15
    Queue<Node> bfs = new LinkedList<>();
16
    Queue<Integer> depths = new LinkedList<>();
17
    bfs.offer(root); depths.offer(1);
18
    int maxDepth = 0;
19
    while (!bfs.isEmpty()) {
20
        Node node = bfs.poll();
21
        int d = depths.poll();
22
        maxDepth = Math.max(maxDepth, d);
23
        // Group each node under its depth so queries can jump straight to qualifying
24
        // nodes.
25
        buckets.computeIfAbsent(d, x -> new ArrayList<>()).add(node);
26
        if (node.left != null)  { bfs.offer(node.left);  depths.offer(d + 1); }
27
        if (node.right != null) { bfs.offer(node.right); depths.offer(d + 1); }
28
    }
29
 
30
    int[][] result = new int[queries.length][];
31
    for (int q = 0; q < queries.length; q++) {
32
        int k = queries[q];
33
        // Iterate exactly depths k, 2k, 3k, … — no per-node modulo test.
34
        for (int d = k; d <= maxDepth; d += k) {        // depths k, 2k, 3k, ...
35
            for (Node node : buckets.getOrDefault(d, List.of())) {
36
                // Swap the child links directly on the bucketed node.
37
                Node tmp = node.left; node.left = node.right; node.right = tmp;
38
            }
39
        }
40
        result[q] = inorderIterative(root);
41
    }
42
    return result;
43
}
44
 
45
private int[] inorderIterative(Node root) {
46
    List<Integer> out = new ArrayList<>();
47
    Deque<Node> stack = new ArrayDeque<>();
48
    Node cur = root;
49
    while (cur != null || !stack.isEmpty()) {
50
        // Iterative inorder left-spine push — avoids deep recursion on skewed trees.
51
        while (cur != null) { stack.push(cur); cur = cur.left; }
52
        cur = stack.pop();
53
        out.add(cur.val);
54
        cur = cur.right;
55
    }
56
    return out.stream().mapToInt(Integer::intValue).toArray();
57
}

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

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

Precomputing depth buckets turns 'find all nodes at depth multiples of k' into a direct lookup instead of a search, and pairs naturally with an iterative inorder to stay safe on deep trees. Depth never changes under child swaps, so the buckets are computed once and reused.

ComplexityO(n·q) time, O(n) space — BFS to bucket depths is O(n) once. Per query you still touch O(n) nodes in the worst case (k=1 swaps every node) plus O(n) iterative inorder → O(n·q). Space O(n) for buckets and the inorder stack.

E · Edge cases and pitfalls6k = maxDepth — Only the deepest bucket swaps (leaves) → usually no visible change.Explore edge cases

Edge cases handled

k = maxDepthOnly the deepest bucket swaps (leaves) → usually no visible change.
k = 1Every bucket swaps — equivalent to mirroring the whole tree.
Deeply skewed tree (~1024 deep)Iterative inorder avoids recursion-depth issues.

Pitfalls

Recomputing buckets every query — unnecessary; depth is invariant, build them once.
Looping depths from 0 instead of k, or mishandling the maxDepth bound.
Forgetting swaps are cumulative even in the bucket version.

Practice

Try the solution yourself

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

Editable code previewimport java.util.*; public int[][] swapNodes(int[][] indexes, int[] queries) { int n = indexes.length; Node[] nodes = new Node[n + 1];Explore the playground

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

import java.util.*;

public int[][] swapNodes(int[][] indexes, int[] queries) {
    int n = indexes.length;
    Node[] nodes = new Node[n + 1];
    for (int i = 1; i <= n; i++) nodes[i] = new Node(i);
    for (int i = 1; i <= n; i++) {
        if (indexes[i - 1][0] != -1) nodes[i].left = nodes[indexes[i - 1][0]];
        if (indexes[i - 1][1] != -1) nodes[i].right = nodes[indexes[i - 1][1]];
    }
    Node root = nodes[1];

// BFS: bucket nodes by depth (depth never changes under swaps)
    Map<Integer, List<Node>> buckets = new HashMap<>();
    Queue<Node> bfs = new LinkedList<>();
    Queue<Integer> depths = new LinkedList<>();
    bfs.offer(root); depths.offer(1);
    int maxDepth = 0;
    while (!bfs.isEmpty()) {
        Node node = bfs.poll();
        int d = depths.poll();
        maxDepth = Math.max(maxDepth, d);
        buckets.computeIfAbsent(d, x -> new ArrayList<>()).add(node);
        if (node.left != null)  { bfs.offer(node.left);  depths.offer(d + 1); }
        if (node.right != null) { bfs.offer(node.right); depths.offer(d + 1); }
    }

int[][] result = new int[queries.length][];
    for (int q = 0; q < queries.length; q++) {
        int k = queries[q];
        for (int d = k; d <= maxDepth; d += k) {        // depths k, 2k, 3k, ...
            for (Node node : buckets.getOrDefault(d, List.of())) {
                Node tmp = node.left; node.left = node.right; node.right = tmp;
            }
        }
        result[q] = inorderIterative(root);
    }
    return result;
}

private int[] inorderIterative(Node root) {
    List<Integer> out = new ArrayList<>();
    Deque<Node> stack = new ArrayDeque<>();
    Node cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) { stack.push(cur); cur = cur.left; }
        cur = stack.pop();
        out.add(cur.val);
        cur = cur.right;
    }
    return out.stream().mapToInt(Integer::intValue).toArray();
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Resetting the tree between queries

Swaps are cumulative. Rebuilding before each query yields wrong answers — two k=1 queries should flip then un-flip, which only works if the second query sees the first query's result.

Explore the code comparison

Don't write this

for k in queries:
    root = build(indexes)        # WRONG: rebuilds, loses cumulative swaps
    swap_at_depth(root, 1, k)
    result.append(inorder(root))

Write this instead

root = build(indexes)            # build ONCE
for k in queries:
    swap_at_depth(root, 1, k)    # mutate the same persistent tree
    result.append(inorder(root))

Depth off-by-one

The root must be depth 1. Starting depth at 0 makes the root match depth % k == 0 for k=1 incorrectly and shifts every level, swapping the wrong depths.

Explore the code comparison

Don't write this

swapAtDepth(root, 0, k);   // root treated as depth 0

Write this instead

swapAtDepth(root, 1, k);   // root is depth 1 per the problem

Mis-mapping the 1-based index array

Row i−1 of the array describes node i. Using indexes[i] for node i shifts every node's children by one, producing a wrong tree.

Explore the code comparison

Don't write this

l, r = indexes[i]          # off by one for 1-based node i

Write this instead

l, r = indexes[i - 1]      # row i-1 holds node i's children

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Build tree from index list, then per-query depth-multiple child swaps + inorder

Code pattern to memorize

def swap_at_depth(node, depth, k):
    if node is None: return
    if depth % k == 0: node.left, node.right = node.right, node.left
    swap_at_depth(node.left,  depth + 1, k)
    swap_at_depth(node.right, depth + 1, k)
# per query k: swap_at_depth(root, 1, k); record inorder(root)

Rules to remember

1Indexing is 1-based: array row i (1..n) gives node i's children; the root is node 1 at depth 1.
2A child value of −1 means that child is absent (null).
3Swap children at depths k, 2k, 3k, … — the test is depth % k == 0.
4Swaps are cumulative across queries — mutate one persistent tree; never rebuild between queries.
5After each query emit the inorder traversal (Left, Node, Right).

Use this pattern when

A tree given as an adjacency/index list you must materialize first
Repeated structural mutations followed by a traversal report
Any 'apply an operation by level/depth, then read the tree' simulation
Mirror-by-level operations on a binary tree

Choose another pattern when

A single static traversal with no mutation → just inorder, skip the swap machinery
Mutations defined per-node, not per-depth → the depth % k shortcut doesn't apply
Tree already given by pointers → skip the index-array construction
Only the final tree shape matters, not each query's output → could fold queries

Interview takeaway

Swap Nodes stitches two skills: constructing a tree from a 1-indexed child-index array, and a depth-aware DFS that mutates then reports. The gotcha is that swaps accumulate — keep one tree and keep mutating it, reading inorder after each query.

Continue

Transfer the pattern to another problem

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

Transferable patternConstruct a tree from an index list, then run depth-conditioned mutations followed by a traversal report. The depth % k == 0 swap rule and cumulative semantics are the crux; depth buckets via BFS locate qualifying nodes directly, and an iterative inorder keeps deep trees safe. It blends tree construction, level/depth processing, and inorder traversal.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Tree: Preorder Traversal

mediumTreesSometimes asked

Swap Nodes [Algo]

Trees & BST · 41 of 41 · 11 min

Return the list of inorder traversals, one per query.

In plain English

Examples

Example 1

Input: indexes = [[2,3],[-1,4],[5,-1],[-1,-1],[-1,-1]], queries = [2]
Output: 4 2 1 3 5
Note: Tree: 1→(2,3); 2→right 4; 3→left 5. Depth-2 nodes are 2 and 3. Swap them: node 2 now has left 4, node 3 now has right 5. Inorder = 4 2 1 3 5.

Example 2

Input: indexes = [[2,3],[-1,-1],[-1,-1]], queries = [1,1]
Output: 3 1 2 / 2 1 3
Note: k=1 swaps every depth. After the first query the root's children flip to (3,2) → inorder 3 1 2. The second k=1 flips them back → 2 1 3. Cumulative.

Example 3

Input: indexes = [[2,3],[-1,-1],[-1,-1]], queries = [2]
Output: 2 1 3
Note: Only depth-2 nodes (2,3) qualify, and they're leaves with nothing to swap, so the tree is unchanged. Inorder 2 1 3.

Constraints

1 ≤ n ≤ 1024 (number of nodes)
1 ≤ number of queries ≤ 1024
1 ≤ k ≤ n for each query
Node values are the node indices 1..n; the root is node 1 at depth 1
Swaps are cumulative across queries

Clarifying questions4First question: Is the index array 0-based or 1-based?Explore questions

Q1.Is the index array 0-based or 1-based?
Node ids are 1-based and the root is node 1 at depth 1. Row i of the array describes node i's children, so array index i−1 holds node i's row. Getting this mapping right is essential.
Q2.Do swaps reset between queries?
No — they are cumulative. Each query swaps on top of all previous swaps, so you mutate one persistent tree rather than rebuilding.
Q3.What depth is the root, and how is 'multiple of k' tested?
Root depth is 1. A node at depth d is swapped when d % k == 0, covering depths k, 2k, 3k, and so on.
Q4.What does −1 mean in a child slot?
No child there — wire it as null. Swapping a node with one or zero children just moves the existing/absent links, which is harmless.

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

Where candidates slip

Rebuilding/resetting the tree between queries (treating each independently), off-by-one in depth (root at depth 0 vs 1), or mis-mapping the 1-based index array to node objects.

How to stand out

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	Build + Recursive Depth-Swap + Inorder (Canonical)	`O(n·q)`	`O(n)`	The standard, clean solution. Lead with it; it cleanly separates the three concerns.	Read
2	Build + BFS Depth Buckets + Iterative InorderOptimal	`O(n·q)`	`O(n)`	Offer if recursion depth is a worry (skewed tree up to ~1024 deep) or to show an explicit, stack-free traversal.	Read

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

Build + Recursive Depth-Swap + Inorder (Canonical)

TimeO(n·q)SpaceO(n)

The standard, clean solution. Lead with it; it cleanly separates the three concerns.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

First materialize the tree: create n node objects (1-based) and wire each node's children from its row, treating −1 as null. The root is node 1.

2Hint 2Explore hint

For a query k, recurse from the root tracking depth (starting at 1). At any node where depth % k == 0, swap its left and right child pointers.

3Hint 3Explore hint

After the swap pass, run a normal inorder traversal to collect the values. Do NOT rebuild between queries — swaps accumulate.

A · Core idea

The problem decomposes into three independent pieces; solving each cleanly is what makes it manageable.

3. Inorder after each query. Once the swaps for query k are applied, run a standard Left-Node-Right inorder to read the current tree and store that as this query's answer.

B · Visual dry run

Interactive dry run

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

indexes = [[2,3],[-1,4],[5,-1],[-1,-1],[-1,-1]], queries = [2]

Before and after k=2 swap

How to read it:Depth-2 nodes 2 and 3 swap children; inorder becomes 4 2 1 3 5.

Rendering diagram…

Final result4 2 1 3 5

C · Code with teaching comments

Reference implementation previewimport java.util.*; class Node { int val; Node left;Explore the full code

solution.javaJava

Build + Recursive Depth-Swap + Inorder (Canonical) — reference

5 teaching notes

1
import java.util.*;
2
 
3
class Node {
4
    int val;
5
    Node left;
6
    Node right;
7
    Node(int val) { this.val = val; }
8
}
9
 
10
public int[][] swapNodes(int[][] indexes, int[] queries) {
11
    int n = indexes.length;
12
    // Size n+1 so we can index 1-based (nodes[1]..nodes[n]); nodes[0] stays unused.
13
    Node[] nodes = new Node[n + 1];           // 1-based: nodes[i] is node i
14
    for (int i = 1; i <= n; i++) nodes[i] = new Node(i);
15
    for (int i = 1; i <= n; i++) {
16
        // Row i−1 of the array holds node i's children — the 1-based-to-0-based bridge.
17
        int l = indexes[i - 1][0];            // row i-1 describes node i
18
        int r = indexes[i - 1][1];
19
        // −1 means no child; otherwise link to the already-created node object.
20
        if (l != -1) nodes[i].left = nodes[l];
21
        if (r != -1) nodes[i].right = nodes[r];
22
    }
23
    Node root = nodes[1];                     // root is node 1, depth 1
24
 
25
    int[][] result = new int[queries.length][];
26
    for (int q = 0; q < queries.length; q++) {
27
        // Mutate the SAME tree each query — swaps are cumulative.
28
        swapAtDepth(root, 1, queries[q]);     // cumulative mutation
29
        List<Integer> out = new ArrayList<>();
30
        inorder(root, out);
31
        result[q] = out.stream().mapToInt(Integer::intValue).toArray();
32
    }
33
    return result;
34
}
35
 
36
private void swapAtDepth(Node node, int depth, int k) {
37
    if (node == null) return;
38
    // Swap only at depths that are multiples of k (k, 2k, 3k, …).
39
    if (depth % k == 0) {                     // swap child LINKS
40
        Node tmp = node.left;
41
        node.left = node.right;
42
        node.right = tmp;
43
    }
44
    swapAtDepth(node.left, depth + 1, k);
45
    swapAtDepth(node.right, depth + 1, k);
46
}
47
 
48
private void inorder(Node node, List<Integer> out) {
49
    if (node == null) return;
50
    inorder(node.left, out);
51
    out.add(node.val);
52
    inorder(node.right, out);
53
}

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

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

E · Edge cases and pitfalls6k larger than the tree's depth — No node satisfies depth % k == 0 → tree unchanged, inorder is the original.Explore edge cases

Edge cases handled

k larger than the tree's depthNo node satisfies depth % k == 0 → tree unchanged, inorder is the original.
Two consecutive k=1 queriesEvery depth swaps then swaps back → second inorder equals the original.
Node with one child swappedThe existing child moves to the other side; the null moves too — still valid.

Pitfalls

Rebuilding or resetting the tree between queries — breaks the cumulative semantics.
Off-by-one on depth: root must be depth 1, so depth % k uses 1-based depth.
Mis-mapping the 1-based index array (using indexes[i] for node i instead of indexes[i−1]).

03.2

Approach 2 of 2 · Optimal

Build + BFS Depth Buckets + Iterative Inorder

TimeO(n·q)SpaceO(n)

Offer if recursion depth is a worry (skewed tree up to ~1024 deep) or to show an explicit, stack-free traversal.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Run one BFS after building to group nodes by depth into buckets.

2Hint 2Explore hint

For a query k, iterate only the buckets at depths k, 2k, 3k, … and swap those nodes' children directly — no full DFS needed.

3Hint 3Explore hint

Use an explicit-stack iterative inorder so a deep, skewed tree can't overflow the call stack.

A · Core idea

Same three phases, but with two robustness tweaks that matter when the tree is deep.

Bucket nodes by depth. After building, run a BFS from the root tracking depth, pushing each node into buckets[depth]. This precomputes, once, which nodes live at each depth.

Still cumulative. As before, the single tree is mutated in place across queries; bucketing is just a faster way to locate the nodes to swap.

B · Visual dry run

Interactive dry run

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

indexes = [[2,3],[-1,4],[5,-1],[-1,-1],[-1,-1]], queries = [2]

Interactive diagram

Depth buckets

bucket

Active call / nodeSupporting contextReturned stateNot active

Nodes grouped by depth once; query k swaps buckets at k, 2k, 3k…

Final result4 2 1 3 5

C · Code with teaching comments

solution.javaJava

Build + BFS Depth Buckets + Iterative Inorder — optimal

4 teaching notes

1
import java.util.*;
2
 
3
public int[][] swapNodes(int[][] indexes, int[] queries) {
4
    int n = indexes.length;
5
    Node[] nodes = new Node[n + 1];
6
    for (int i = 1; i <= n; i++) nodes[i] = new Node(i);
7
    for (int i = 1; i <= n; i++) {
8
        if (indexes[i - 1][0] != -1) nodes[i].left = nodes[indexes[i - 1][0]];
9
        if (indexes[i - 1][1] != -1) nodes[i].right = nodes[indexes[i - 1][1]];
10
    }
11
    Node root = nodes[1];
12
 
13
    // BFS: bucket nodes by depth (depth never changes under swaps)
14
    Map<Integer, List<Node>> buckets = new HashMap<>();
15
    Queue<Node> bfs = new LinkedList<>();
16
    Queue<Integer> depths = new LinkedList<>();
17
    bfs.offer(root); depths.offer(1);
18
    int maxDepth = 0;
19
    while (!bfs.isEmpty()) {
20
        Node node = bfs.poll();
21
        int d = depths.poll();
22
        maxDepth = Math.max(maxDepth, d);
23
        // Group each node under its depth so queries can jump straight to qualifying
24
        // nodes.
25
        buckets.computeIfAbsent(d, x -> new ArrayList<>()).add(node);
26
        if (node.left != null)  { bfs.offer(node.left);  depths.offer(d + 1); }
27
        if (node.right != null) { bfs.offer(node.right); depths.offer(d + 1); }
28
    }
29
 
30
    int[][] result = new int[queries.length][];
31
    for (int q = 0; q < queries.length; q++) {
32
        int k = queries[q];
33
        // Iterate exactly depths k, 2k, 3k, … — no per-node modulo test.
34
        for (int d = k; d <= maxDepth; d += k) {        // depths k, 2k, 3k, ...
35
            for (Node node : buckets.getOrDefault(d, List.of())) {
36
                // Swap the child links directly on the bucketed node.
37
                Node tmp = node.left; node.left = node.right; node.right = tmp;
38
            }
39
        }
40
        result[q] = inorderIterative(root);
41
    }
42
    return result;
43
}
44
 
45
private int[] inorderIterative(Node root) {
46
    List<Integer> out = new ArrayList<>();
47
    Deque<Node> stack = new ArrayDeque<>();
48
    Node cur = root;
49
    while (cur != null || !stack.isEmpty()) {
50
        // Iterative inorder left-spine push — avoids deep recursion on skewed trees.
51
        while (cur != null) { stack.push(cur); cur = cur.left; }
52
        cur = stack.pop();
53
        out.add(cur.val);
54
        cur = cur.right;
55
    }
56
    return out.stream().mapToInt(Integer::intValue).toArray();
57
}

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

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

E · Edge cases and pitfalls6k = maxDepth — Only the deepest bucket swaps (leaves) → usually no visible change.Explore edge cases

Edge cases handled

k = maxDepthOnly the deepest bucket swaps (leaves) → usually no visible change.
k = 1Every bucket swaps — equivalent to mirroring the whole tree.
Deeply skewed tree (~1024 deep)Iterative inorder avoids recursion-depth issues.

Pitfalls

Recomputing buckets every query — unnecessary; depth is invariant, build them once.
Looping depths from 0 instead of k, or mishandling the maxDepth bound.
Forgetting swaps are cumulative even in the bucket version.

Practice

Try the solution yourself

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

Editable code previewimport java.util.*; public int[][] swapNodes(int[][] indexes, int[] queries) { int n = indexes.length; Node[] nodes = new Node[n + 1];Explore the playground

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

import java.util.*;

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Resetting the tree between queries

Swaps are cumulative. Rebuilding before each query yields wrong answers — two k=1 queries should flip then un-flip, which only works if the second query sees the first query's result.

Explore the code comparison

Don't write this

for k in queries:
    root = build(indexes)        # WRONG: rebuilds, loses cumulative swaps
    swap_at_depth(root, 1, k)
    result.append(inorder(root))

Write this instead

root = build(indexes)            # build ONCE
for k in queries:
    swap_at_depth(root, 1, k)    # mutate the same persistent tree
    result.append(inorder(root))

Depth off-by-one

The root must be depth 1. Starting depth at 0 makes the root match depth % k == 0 for k=1 incorrectly and shifts every level, swapping the wrong depths.

Explore the code comparison

Don't write this

swapAtDepth(root, 0, k);   // root treated as depth 0

Write this instead

swapAtDepth(root, 1, k);   // root is depth 1 per the problem

Mis-mapping the 1-based index array

Row i−1 of the array describes node i. Using indexes[i] for node i shifts every node's children by one, producing a wrong tree.

Explore the code comparison

Don't write this

l, r = indexes[i]          # off by one for 1-based node i

Write this instead

l, r = indexes[i - 1]      # row i-1 holds node i's children

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Build tree from index list, then per-query depth-multiple child swaps + inorder

Code pattern to memorize

def swap_at_depth(node, depth, k):
    if node is None: return
    if depth % k == 0: node.left, node.right = node.right, node.left
    swap_at_depth(node.left,  depth + 1, k)
    swap_at_depth(node.right, depth + 1, k)
# per query k: swap_at_depth(root, 1, k); record inorder(root)

Rules to remember

1Indexing is 1-based: array row i (1..n) gives node i's children; the root is node 1 at depth 1.
2A child value of −1 means that child is absent (null).
3Swap children at depths k, 2k, 3k, … — the test is depth % k == 0.
4Swaps are cumulative across queries — mutate one persistent tree; never rebuild between queries.
5After each query emit the inorder traversal (Left, Node, Right).

Use this pattern when

A tree given as an adjacency/index list you must materialize first
Repeated structural mutations followed by a traversal report
Any 'apply an operation by level/depth, then read the tree' simulation
Mirror-by-level operations on a binary tree

Choose another pattern when

A single static traversal with no mutation → just inorder, skip the swap machinery
Mutations defined per-node, not per-depth → the depth % k shortcut doesn't apply
Tree already given by pointers → skip the index-array construction
Only the final tree shape matters, not each query's output → could fold queries

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

Same pattern

←

Tree: Preorder Traversal