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 first 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* (just exchange the pointers; you don't move values). 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 off 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 just keep applying swaps — the second example (k=1 then k=1 flips and 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 of the DFS version. 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 · 34 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. depth 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 (mapping 1-based node ids to node objects and wiring 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: 2 now has left 4, 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 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. Get this mapping right or the whole tree is wrong.
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 a null pointer. Swapping a node with one or zero children just moves the existing/absent links.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Build the tree from the index array (node i's two children are given by row i, with −1 meaning no child; the root is node 1 at depth 1). For each query k, swap the left and right children of every node whose depth is a multiple of k (k, 2k, 3k, …), then print the inorder traversal of the resulting tree. Crucially, the swaps are CUMULATIVE — each query operates on the tree as left by the previous one. Build is O(n); each query is O(n) for the depth-swap DFS 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 at depth % k == 0), and produce an inorder traversal — while remembering swaps accumulate.

Where candidates slip

Resetting the tree between queries (treating each query independently), off-by-one in depth (root at depth 0 vs 1), or mis-mapping the 1-based index array to nodes.

How to stand out

Separate the three concerns cleanly — build once, swap-by-depth per query, inorder per query — and explicitly note that swaps are cumulative so you mutate a single shared tree.

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, do a normal inorder traversal to collect the values. Remember NOT to 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 first 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 (just exchange the pointers; you don't move values). 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 off 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 just keep applying swaps — the second example (k=1 then k=1 flips and 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
    Node[] nodes = new Node[n + 1];           // 1-based: nodes[i] is node i
13
    for (int i = 1; i <= n; i++) nodes[i] = new Node(i);
14
    for (int i = 1; i <= n; i++) {
15
        int l = indexes[i - 1][0];            // row i-1 describes node i
16
        int r = indexes[i - 1][1];
17
        // −1 means no child; otherwise link to the already-created node object.
18
        if (l != -1) nodes[i].left = nodes[l];
19
        if (r != -1) nodes[i].right = nodes[r];
20
    }
21
    Node root = nodes[1];                     // root is node 1, depth 1
22
 
23
    int[][] result = new int[queries.length][];
24
    for (int q = 0; q < queries.length; q++) {
25
        swapAtDepth(root, 1, queries[q]);     // cumulative mutation
26
        List<Integer> out = new ArrayList<>();
27
        inorder(root, out);
28
        result[q] = out.stream().mapToInt(Integer::intValue).toArray();
29
    }
30
    return result;
31
}
32
 
33
private void swapAtDepth(Node node, int depth, int k) {
34
    if (node == null) return;
35
    if (depth % k == 0) {                     // swap child LINKS
36
        Node tmp = node.left;
37
        node.left = node.right;
38
        node.right = tmp;
39
    }
40
    swapAtDepth(node.left, depth + 1, k);
41
    swapAtDepth(node.right, depth + 1, k);
42
}
43
 
44
private void inorder(Node node, List<Integer> out) {
45
    if (node == null) return;
46
    inorder(node.left, out);
47
    out.add(node.val);
48
    inorder(node.right, out);
49
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.49 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 and 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 record each node's depth (or 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 the 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 of the DFS version. 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
        for (int d = k; d <= maxDepth; d += k) {        // depths k, 2k, 3k, ...
34
            for (Node node : buckets.getOrDefault(d, List.of())) {
35
                // Swap the child links directly on the bucketed node.
36
                Node tmp = node.left; node.left = node.right; node.right = tmp;
37
            }
38
        }
39
        result[q] = inorderIterative(root);
40
    }
41
    return result;
42
}
43
 
44
private int[] inorderIterative(Node root) {
45
    List<Integer> out = new ArrayList<>();
46
    Deque<Node> stack = new ArrayDeque<>();
47
    Node cur = root;
48
    while (cur != null || !stack.isEmpty()) {
49
        // Iterative inorder left-spine push — avoids deep recursion on skewed trees.
50
        while (cur != null) { stack.push(cur); cur = cur.left; }
51
        cur = stack.pop();
52
        out.add(cur.val);
53
        cur = cur.right;
54
    }
55
    return out.stream().mapToInt(Integer::intValue).toArray();
56
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.56 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 using <= incorrectly on maxDepth.
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 — e.g. 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

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

swapAtDepth(node, depth, k):
    if node is null: return
    if depth % k == 0: swap node.left, node.right
    swapAtDepth(node.left, depth+1, k)
    swapAtDepth(node.right, depth+1, k)
# per query k: swapAtDepth(root,1,k); then inorder(root)

Rules to remember

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

Use this pattern when

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

Choose another pattern when

Single static traversal with no mutation → plain inorder, skip the swap machinery
Mutations defined per-node not per-depth → can't use the depth % k shortcut
Tree given by pointers already → skip the index-array construction step

Interview takeaway

This problem is two skills stitched together: constructing a tree from a 1-indexed child-index array, and a depth-aware DFS that mutates then reports. The cumulative-swap detail is the gotcha — keep one tree and keep mutating it.

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 let you 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

←

Is This a Binary Search Tree?

Continue · Next problem

Tree: Height of a Binary Tree

mediumTreesSometimes asked

Swap Nodes [Algo]

Trees & BST · 34 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: 2 now has left 4, 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 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. Get this mapping right or the whole tree is wrong.
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 a null pointer. Swapping a node with one or zero children just moves the existing/absent links.

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

Resetting the tree between queries (treating each query independently), off-by-one in depth (root at depth 0 vs 1), or mis-mapping the 1-based index array to nodes.

How to stand out

Separate the three concerns cleanly — build once, swap-by-depth per query, inorder per query — and explicitly note that swaps are cumulative so you mutate a single shared tree.

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, do a normal inorder traversal to collect the values. Remember NOT to 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 off 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
    Node[] nodes = new Node[n + 1];           // 1-based: nodes[i] is node i
13
    for (int i = 1; i <= n; i++) nodes[i] = new Node(i);
14
    for (int i = 1; i <= n; i++) {
15
        int l = indexes[i - 1][0];            // row i-1 describes node i
16
        int r = indexes[i - 1][1];
17
        // −1 means no child; otherwise link to the already-created node object.
18
        if (l != -1) nodes[i].left = nodes[l];
19
        if (r != -1) nodes[i].right = nodes[r];
20
    }
21
    Node root = nodes[1];                     // root is node 1, depth 1
22
 
23
    int[][] result = new int[queries.length][];
24
    for (int q = 0; q < queries.length; q++) {
25
        swapAtDepth(root, 1, queries[q]);     // cumulative mutation
26
        List<Integer> out = new ArrayList<>();
27
        inorder(root, out);
28
        result[q] = out.stream().mapToInt(Integer::intValue).toArray();
29
    }
30
    return result;
31
}
32
 
33
private void swapAtDepth(Node node, int depth, int k) {
34
    if (node == null) return;
35
    if (depth % k == 0) {                     // swap child LINKS
36
        Node tmp = node.left;
37
        node.left = node.right;
38
        node.right = tmp;
39
    }
40
    swapAtDepth(node.left, depth + 1, k);
41
    swapAtDepth(node.right, depth + 1, k);
42
}
43
 
44
private void inorder(Node node, List<Integer> out) {
45
    if (node == null) return;
46
    inorder(node.left, out);
47
    out.add(node.val);
48
    inorder(node.right, out);
49
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.49 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 record each node's depth (or 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 the 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
        for (int d = k; d <= maxDepth; d += k) {        // depths k, 2k, 3k, ...
34
            for (Node node : buckets.getOrDefault(d, List.of())) {
35
                // Swap the child links directly on the bucketed node.
36
                Node tmp = node.left; node.left = node.right; node.right = tmp;
37
            }
38
        }
39
        result[q] = inorderIterative(root);
40
    }
41
    return result;
42
}
43
 
44
private int[] inorderIterative(Node root) {
45
    List<Integer> out = new ArrayList<>();
46
    Deque<Node> stack = new ArrayDeque<>();
47
    Node cur = root;
48
    while (cur != null || !stack.isEmpty()) {
49
        // Iterative inorder left-spine push — avoids deep recursion on skewed trees.
50
        while (cur != null) { stack.push(cur); cur = cur.left; }
51
        cur = stack.pop();
52
        out.add(cur.val);
53
        cur = cur.right;
54
    }
55
    return out.stream().mapToInt(Integer::intValue).toArray();
56
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.56 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 using <= incorrectly on maxDepth.
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 — e.g. 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

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

swapAtDepth(node, depth, k):
    if node is null: return
    if depth % k == 0: swap node.left, node.right
    swapAtDepth(node.left, depth+1, k)
    swapAtDepth(node.right, depth+1, k)
# per query k: swapAtDepth(root,1,k); then inorder(root)

Rules to remember

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

Use this pattern when

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

Choose another pattern when

Single static traversal with no mutation → plain inorder, skip the swap machinery
Mutations defined per-node not per-depth → can't use the depth % k shortcut
Tree given by pointers already → skip the index-array construction step

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

←

Is This a Binary Search Tree?

Continue · Next problem

Tree: Height of a Binary Tree