private static Node createTree(Node root, List<List<Integer>> indexes)
    {
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 0;
        while(!queue.isEmpty() && (i < indexes.size()))
        {
            List<Integer> index = indexes.get(i++);
            Node n = queue.remove();
            if(index.get(0) > 1)
            {
                n.left = new Node(index.get(0));
                queue.add(n.left);
            }
            if(index.get(1) > 1)
            {
                n.right = new Node(index.get(1));
                queue.add(n.right);
            } 
        } 
        return root;
    } 
    
    private static void inOrder(Node root, List<Integer> indexes)
    {
        if(root == null)
            return;
        inOrder(root.left, indexes);
        indexes.add(root.data); 
        inOrder(root.right, indexes);
    }
    
    private static void swap(Node root, int level, int query)
    {
        if((root == null) || root.left == root.right)
            return;
        if((level % query) == 0)
        {
            Node a = root.left;
            root.left = root.right;
            root.right = a;
        }
        swap(root.left, level+1, query);
        swap(root.right, level+1, query);
    }
    
     public static List<List<Integer>> swapNodes(List<List<Integer>> indexes, List<Integer> queries) {
    // Write your code here
        List<List<Integer>> result = new ArrayList<>();
        Node root = new Node(1);
        createTree(root, indexes);
        for(Integer q : queries)
        {
            List<Integer> list = new ArrayList<>();
            swap(root, 1, q);
            inOrder(root, list);
            result.add(list);
        }
         
        return result;
    }

sys.setrecursionlimit(1 << 30)
def create_tree(indexes):
    tree_arr = [-1 for _ in range(1025)]
    tree_arr[1] = 1

    _next = []
    frontier = [1]
    indexes_pos = 0
    while frontier:
        for v in frontier:

            if indexes_pos >= len(indexes):
                return tree_arr

            if v != -1:
                left_c, right_c = indexes[indexes_pos][0], indexes[indexes_pos][1]
                tree_arr[v] = [left_c, right_c]
                _next.append(left_c)
                _next.append(right_c)
                indexes_pos += 1

        frontier = _next
        _next = []

    return tree_arr


def swapNodes(indexes, queries):
    tree = create_tree(indexes)
    height = 1025
    controller = [0 for _ in range(height)]
    traverse_res = []
    
    def traverse(lvl, idx):
        if idx >= len(tree) or idx == -1:
            return
            
        left = tree[idx][0]
        right = tree[idx][1]
        if controller[lvl] == 1:
            left = tree[idx][1]
            right = tree[idx][0]
            
        traverse(lvl+1, left)
        traverse_res.append(idx)
        traverse(lvl+1, right)
        
        return
    
    res = []
    for q in queries:
        tmp = q
        while q < height-1:
            controller[q-1] = not controller[q-1]
            q += tmp
        traverse(0, 1)
        res.append(traverse_res)
        traverse_res = []
				
        
    return res
        

from collections import deque
sys.setrecursionlimit(500000)

#
# Complete the 'swapNodes' function below.
#
# The function is expected to return a 2D_INTEGER_ARRAY.
# The function accepts following parameters:
#  1. 2D_INTEGER_ARRAY indexes
#  2. INTEGER_ARRAY queries
#

class node:
    def __init__(self, info, depth):
        self.info = info
        self.depth = depth
        self.left = None
        self.right = None
        
def createTree(indexes):
    q = deque()
    root = node(1, 1)
    q.append(root)
    
    for x in indexes:
        ele = q.popleft()
        if x[0] != -1:
            ele.left = node(x[0], ele.depth + 1)
            q.append(ele.left)
        if x[1] != -1:
            ele.right = node(x[1], ele.depth + 1)
            q.append(ele.right)
        if len(q) == 0:
            break
            
    return root
    
    
def inorder(root):
    values = []
    
    def inorder_traversal(root):
        if root is None:
            return
        inorder_traversal(root.left)
        values.append(root.info)
        inorder_traversal(root.right)
        
    inorder_traversal(root)
    return values
        
        
def nodesStack(root):
    stack = [root]
    values = []
    while len(stack) != 0:
        ele = stack.pop()
        values.append(ele)
        if ele.left:
            stack.append(ele.left)
        if ele.right:
            stack.append(ele.right)
            
    return values

def swapNodes(indexes, queries):
    # Write your code here
    root = createTree(indexes)
    nodes = nodesStack(root)
    finalarray = []
    for k in queries:
        for n in nodes:
            if n.depth % k == 0:
                if n.left is None and n.right is None:
                    pass
                elif n.left is None and n.right:
                    n.left = n.right
                    n.right = None
                elif n.right is None and n.left:
                    n.right = n.left
                    n.left = None
                else:
                    temp = n.right
                    n.right = n.left
                    n.left = temp
        finalarray.append(inorder(root))
        
    return finalarray

class Node {
    constructor(val) {
        this.val = val;
        this.levelNum = null;
        this.left = null;
        this.right = null;
    }
}

/**
 * Swap nodes in a binary tree at the levels listed in the queries array.
 * @param {Array<Array<Number>>} indexes
 * @param {Array<Number>} queries
 * @returns {Array<Array<Number>>}
 */
function swapNodes(indexes, queries) {
    if (!indexes?.length || !queries?.length) {
        return [];
    } else if (indexes.length === 1) {
        return indexes;
    }

    // Construct binary tree from indexes (which is a 2-dimensional array)
    const root = new Node(1);
    root.levelNum = 1;
    const buildQueue = [root];
    for (const [leftVal, rightVal] of indexes) {
        const node = buildQueue.shift();
        if (leftVal !== -1) {
            node.left = new Node(leftVal);
            buildQueue.push(node.left);
        }
        if (rightVal !== -1) {
            node.right = new Node(rightVal);
            buildQueue.push(node.right);
        }
    }

    // `factor` is `k` from the instructions
    const allResults = [];
    for (const factor of queries) {
        const result = [];
        traverseInOrderAndSwap(root, factor, result);
        allResults.push(result);
    }

    return allResults;
}

/**
 * Traverse in-order (DFS) and swap the nodes at the appropriate levels.
 * @param {Node} node
 * @param {Number} factor
 * @param {Array<Number>} result
 */
function traverseInOrderAndSwap(node, factor, result) {
    const isSwapLevel = node?.levelNum % factor === 0;
    if (isSwapLevel) {
        const holder = node.left;
        node.left = node.right;
        node.right = holder;
    }

    if (node.left) {
        node.left.levelNum = node.levelNum + 1;
        traverseInOrderAndSwap(node.left, factor, result);
    }
    if (node.val) result.push(node.val);
    if (node.right) {
        node.right.levelNum = node.levelNum + 1;
        traverseInOrderAndSwap(node.right, factor, result);
    }
}