We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Trees
  4. Swap Nodes [Algo]
  5. Discussions

Swap Nodes [Algo]

  • abelw
     + 0 comments

    There are 4 things that need to happen: 1. Build the tree (from the indexes 2D array), using a variation from BFS/level-order traversal (for loop) 2. Loop through the queries (k) to do the following: 2.1. Swap the nodes at the appropriate level 2.2. Traverse in-order in order to push the values into an array to be returned.

    The optimization is that steps 2.1 and 2.2 can be accomplished in a single iteration, resulting in O(n).

    JavaScript

    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);
    }
}