Cloning data structure

Clone a Linked List

We can write recursive code as below.

const clone = head => {
  if(!head) {
    return head;
  }
  const copy = new Node(head.val);
  copy.next = clone(head.next);
  return copy;
}

We can write iterative code as below.

const clone = head => {
  if(!head) {
    return head;
  }
  let duplicate = new Node(head.val);
  let node = head;
  let copy = duplicate;
  while(node.next) {
    copy.next = new Node(node.next.val);
    copy = copy.next;
    node = node.next;
  }
  return duplicate;
}

Clone a Linked List with the next and Random Pointer

https://leetcode.com/problems/copy-list-with-random-pointer/

Node has two pointers

1. One pointer points to the next node
2. The second pointer points to any random node in the list.

The goal is to create a clone of this linked list in O(N) time.

Approach: Create a copy and use the map to store old vs new mapping to build the random pointer

1. Pass 1:
2. Create a duplicate node corresponding to the old node and build the clone of the Linked list without the random pointer.
3. Build a map to store the mapping of map[old]=duplicate
4. Pass 2:
5. Update the random pointer for duplicate nodes using map[old]->random = map[old->random]

Following is the code for reference.

class Node {
  constructor(val, next, random) {
    this.val = val;
    this.next = next;
    this.random = random;
  }
}
const cloneLinkedList = head => {
  if(!head) {
    reutrn null;
  }
  const map = new Map();
  const duplicate = new Node(head.val);
  map.set(head, duplicate);
  // First pass: build duplicate list with next pointer with map
  let node = head;
  let copy = duplicate;
  while(node.next) {
    copy.next = new Node(node.next.val);
    node = node.next;
    copy = copy.next;
    map.set(node, copy);
  }
  // Second pass: Build random pointer
  node = head;
  while(node) {
    map.get(node).random = map.get(node.random);
    node = node.next;
  }
  return duplicate;
}

Clone binary tree

We can use pre-order traversal to create a clone.

const dfs = node => {
  if(!node) {
    return node;
  }
  const copy = new Node(node.val);
  copy.left = clone(node.left);
  copy.right = clone(node.right);
  return copy;
}
const clone = root => {
  return dfs(root);
}

Clone binary tree with random pointer

https://leetcode.com/problems/clone-binary-tree-with-random-pointer/

Each node has three different pointers.

1. left
2. right
3. random

The goal is to deep clone binary tree with random pointer.

We can apply an approach similar to what we discussed above for a list with random pointers. Following are the overall steps.

1. First, create the duplicate tree using dfs preorder to fill only left and right pointer.
2. In the above step, also build a map to build a mapping between old vs duplicate nodes.
3. In the second pass, update the random pointer using map[x].random = map[x->random]

Following is the code for reference.

/**
 * @param {Node} root
 * @return {NodeCopy}
 */
var copyRandomBinaryTree = function(root) {
    if (!root) {
        return root;
    }
    const map = new Map();

    // In first pass build copy and update map
    const dfs = (node) => {
        if(!node) {
            return node;
        }
        // preorder traversal
        const copy = new NodeCopy(node.val); 
        map.set(node, copy);
        copy.left = dfs(node.left);
        copy.right = dfs(node.right);        
        return copy;
    }

    // In second pass, update random link
    const updateRandom = node => {
        if(!node) {
            return copy;
        }
        if(node.random) {
            map.get(node).random = map.get(node.random);         
        }        
        updateRandom(node.left);
        updateRandom(node.right)
    }
    // create copy of tree in first pass
    const copy = dfs(root);
    
    // update reference
    updateRandom(root);
    
    return copy;
};

Clone n-ary tree

https://leetcode.com/problems/clone-n-ary-tree/

We can simply use preorder traversal order to build the deep copy. Following is the code for reference.

/**
 * @param {Node|null} node
 * @return {Node|null}
 */
var cloneTree = function(root) {
    // Base case: empty node
    if(root == null) {
        return root;
    }
    // Create a copy for node
    const copy = new Node(root.val);
    // Clone children
    for (const child of root.children) {
        copy.children.push(cloneTree(child));
    }
    return copy;
};

Clone n-ary into binary tree

https://leetcode.com/problems/encode-n-ary-tree-to-binary-tree/description/

Intuition

1. Preserve all the children of the node.
2. Preserve parent-child relationship.

Based on this we can we can use right pointer for all children as linked list form and left pointer for parent-child. The following are steps.

1. Link all siblings together, like a singly linked list.

2. Link the head of the obtained list of siblings with its parent node.

The above steps complete the conversion to a binary tree :)

The following are steps for the algorithm for encodeimplementation.

1. Use bfs to apply level order linking.
2. Since we need to create a corresponding binary tree node therefore in the queue add pair<node, copy>

Following would be steps for decode

1. Apply bfs to reverse the steps.
2. We start from the root node of the encoded binary tree by pushing it into the queue.
3. At each step of the iteration, we pop out a binary node from the tree, we then take the left child node of the node as its corresponding first child node of the original N-ary node.
4. We then recover the rest of the child nodes by following the right pointer of the binary nodes.

Following is the implementation for this approach.

/**
 * // Definition for a _Node.
 * function _Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

class Codec {
    constructor() {
    }

    /** 
     * @param {Node|null} root
     * @return {TreeNode|null}
     */
    // Encodes an n-ary tree to a binary tree.
    encode = function (root) {
        if (!root) {
            return null;
        }
        const copyRoot = new TreeNode(root.val);
        const queue = [[root, copyRoot]];
        while (queue.length > 0) {
            const [nNode, bNode] = queue.shift();
            // Phase 1: Now encode children nodes into linked list of TreeNode
            let bHead, bPrevChild;
            for (const nChild of nNode.children) {
                const bChild = new TreeNode(nChild.val);
                // Cpature head for linked list first time
                if (!bHead) {
                    bHead = bChild;
                } else {
                    bPrevChild.right = bChild;
                }
                bPrevChild = bChild;
                // Add into queue for bfs
                queue.push([nChild, bChild]);
            }
            // Phase 2: Link the head of linked list to the left node
            bNode.left = bHead;
        }
        return copyRoot;
    };

    /** 
     * @param {TreeNode|null} root 
     * @return {Node|null}
     */
    // Decodes your binary tree to an n-ary tree.
    decode = function (root) {
        if (!root) {
            return null;
        }
        const copyRoot = new Node(root.val, []);
        const queue = [[root, copyRoot]];
        while (queue.length > 0) {
            const [bNode, nNode] = queue.shift();
            // Decode the left node of binary tree as first child
            let sibling = bNode.left;
            while (sibling) {
                const nChild = new Node(sibling.val, []);
                nNode.children.push(nChild);
                // Add child into queue for further decoding
                queue.push([sibling, nChild]);

                // move to right node of binary tree
                sibling = sibling.right;
            }

        }
        return copyRoot;
    };
}

/*
* Your Codec object will be instantiated and called as such:
* codec = Codec()
* codec.decode(codec.encode(root))
*/

Clone a graph

https://leetcode.com/problems/clone-graph/description/

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

class Node {
 public int val;
 public List<Node> neighbors;
}

The following is intuition.

1. n-ary tree doesn’t have a cycle therefore we don’t need to track for a cycle.
2. A graph can have a cycle, therefore needs to track the visited node.
3. We can apply a similar preorder traversal i.e. first process node then start processing the rest of the neighbors.
4. If the node is already visited i.e. already processed i.e. copy was already created then we need to simply return the copy node.
5. Instead of maintaining visited map as <node, boolean> , we will use <old, copy> to serve both purposes i.e. track visited and also track the copy node.

Following is the code to implement this.

/**
 * // Definition for a Node.
 * function Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */

/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function (node) {

    if (!node) {
        return node;
    }
    const visited = new Map();
    const dfs = (node) => {
        // if current node is already visited then return clone
        if (visited.has(node)) {
            return visited.get(node);
        }
        // not visited, create clone
        const clone = new Node(node.val);

        // mark as visited
        visited.set(node, clone);

        // process neighbors
        for (const neighbor of node.neighbors) {
            clone.neighbors.push(dfs(neighbor));
        }
        return clone;
    }
    return dfs(node);
};

Happy learning :-)