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]

Sort by

recency

|

712 Discussions

|

  • tan_191
     + 0 comments

    Here's my solution in C#, which passed all 11 test cases. For each node, you need to keep track of its index, children, and depth, the last one being important for the swap operation since you need to swap every node whose depth is a multiple of the number specified by each query.

    Since the swaps affect nodes individually, you can perform the in-order traversal and the child swaps using the same recursion function.

    public class Node {
        public int root;
        public int left;
        public int right;
        public int depth;
        
        public Node(int n, int a, int b) {
            root = n;
            left = a;
            right = b;
            depth = -1;
        }
    }

    public static List<List<int>> swapNodes(List<List<int>> indexes, List<int> queries)
    {
        List<List<int>> swappedTree = new List<List<int>>();
        List<Node> nodeList = new List<Node>();
        
        for (int i = 0; i < indexes.Count; i++) {
            List<int> index = indexes[i];
            int a = index[0]-1;
            int b = index[1]-1;
            //Console.WriteLine(a + ", " + b);
            nodeList.Add(new Node(i, a, b));
        }
        
        for (int i = 0; i < nodeList.Count; i++) {
            Node currNode = nodeList[i];
            int currentdepth = nodeList[i].depth > 0 ? nodeList[i].depth : 1;
            int a = currNode.left;
            int b = currNode.right;
            if (nodeList[i].depth < 0) nodeList[i].depth = currentdepth;
            if (a > 0) nodeList[a].depth = currentdepth+1;
            if (b > 0) nodeList[b].depth = currentdepth+1;
        }
        
        while (queries.Count > 0) {
            int query = queries[0];
            List<int> inOrderTraversalList = inOrderTraversal(nodeList, 0, query);
            swappedTree.Add(inOrderTraversalList);
            queries.RemoveAt(0);
        }
        
        return swappedTree;
    }
    
    public static List<int> inOrderTraversal(List<Node> nodeList, int nodeIndex, int query) {
        List<int> inOrderTraversalList = new List<int>();
        //Console.WriteLine(nodeIndex);
        if (nodeList[nodeIndex].depth % query == 0) {
            int a = nodeList[nodeIndex].left;
            nodeList[nodeIndex].left = nodeList[nodeIndex].right;
            nodeList[nodeIndex].right = a;
        }
        
        if (nodeList[nodeIndex].left > 0) inOrderTraversalList.AddRange(inOrderTraversal(nodeList, nodeList[nodeIndex].left, query));
        inOrderTraversalList.Add(nodeIndex+1);
        if (nodeList[nodeIndex].right > 0) inOrderTraversalList.AddRange(inOrderTraversal(nodeList, nodeList[nodeIndex].right, query));
        
        return inOrderTraversalList;
    }

  • upanshu21
     + 0 comments

    Never have I ever seen a problem description as poorly written as this one. The fact that this statement has remained as it is for 9 years speak volumes.

  • steven_major
     + 0 comments

    This problem description needs a bit of work - I do appreciate the examples and their clarity as I was able to deduce the actual index recording rules from them. That said, the provided instructions for recording the index values of a tree were wrong.

    From the instructions:

     - it is the first node visited, the first time visited
 - it is a leaf, should only be visited once
 - all of its subtrees have been explored, should only be visited once while this is true
 - it is the root of the tree, the first time visited

    This is not correct (doesn't match their provided solutions). This implies we record the first node visited, which will always be the left or right child of the root node. This also implies that if a node has a left and right child, we record the value of the node only after exploring both the left and right sub-trees. The examples make it clear that this is not the case.

    The actual logic for printing values seems to be: "record an index whenever arriving at a node and its left subtree is fully explored (true if there is no left sub-tree)". Note that this handles leaf nodes since they have no left subtree.

    i.e. the traversal logic to get the indices in the order they want is: traverse tree in an in-order, depth first way. Record the index for a node when arriving at that node AND that node's left subtree has been fully explored - happens when: - arriving at a node and it has no left sub-tree - arriving at a node from its left sub-tree

    I spent most of my time on this problem figuring that part out, which was frustrating

  • g503420777
     + 0 comments

    No need to build a tree. Just swap the numbers in the list.

    sys.setrecursionlimit(2000) 
def swapNodes(indexes, queries):
    # Write your code here
    result = []
    indexes = [[]]+indexes
    for k in queries:
        res = []
        swap(indexes, 0, 1, k, res)
        result.append(res)
    return result

def swap(nodes, depth, curr, k, result):
    if curr == -1: 
        return
    if depth % k == k - 1:
        nodes[curr][0], nodes[curr][1] = nodes[curr][1], nodes[curr][0]
    swap(nodes, depth + 1, nodes[curr][0], k, result)
    result.append(curr)
    swap(nodes, depth + 1, nodes[curr][1], k, result)

  • phongthuypts
     + 0 comments

    Java:

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