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]

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