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

|

727 Discussions

|

  • suxihong07
     + 0 comments

    Python code:

    sys.setrecursionlimit(2000)

    def swapNodes(indexes, queries):

    # Write your code here
result = []

for k in queries:
    res = []
    swap(indexes, 1, 1, k, res)
    result.append(res)

return result

    def swap(indexes, depth, idx, k, res):

    if idx == -1:
    return

if depth % k == 0:
    indexes[idx - 1][0], indexes[idx - 1][1] = indexes[idx - 1][1], indexes[idx - 1][0]
# In-order traverse
swap(indexes, depth + 1,indexes[idx - 1][0], k, res)
res.append(idx)
swap(indexes, depth + 1, indexes[idx - 1][1], k, res)

  • tan_191
     + 0 comments

    C# solution using a Dictionary and Depth-First Search:

    The below solution passes all eleven test cases, all of which execute in at most one second.

    The use of a Dictionary < int, int[] > object to keep track of the node indices helps ensure that the algorithm will skip any node child with a value of -1 (i.e. no child), since the key values stored have a value of at least 1 by default. The value corresponding to each key is an integer array containing the depth of the node at index 0 and the indices of its children (if any) at indices 1 and 2. The DFS traversal algorithm checks if the depth is divisible by the current query value, and if such is the case, the values at indices 1 and 2 are switched before the DFS recurs. Using a dictionary and checking if the key is contained in the node list means we won't have to worry about exceptions due to accessing indices outside of the range of the tree.

    public static List<List<int>> swapNodes(List<List<int>> indexes, List<int> queries)
    {
        //The tree dictionary used for this solution has the index for each node as a key, and the depth and children of this node stored in an int[] array as the corresponding value.
        Dictionary<int, int[]> tree = new Dictionary<int, int[]>();
        
        //First, initialize the nodes using one-indexing for the keys in the dictionary. Each value is an int[3] array whose items are { depth, left child index, right child index }.
        for (int n = 0; n < indexes.Count; n++) {
            List<int> i = indexes[n];
            tree.Add(n+1,new int[3]{1, i[0], i[1]});
        }
        
        //Now set the depths for each node. We don't have to sort the list of keys necessarily, though a SortedDictionary object can be used instead of a Dictionary if you want to play it safer.
        foreach (int curr in tree.Keys) {
            int l = tree[curr][1], r = tree[curr][2];
            if (l > 0) tree[l][0] = tree[curr][0] + 1;
            if (r > 0) tree[r][0] = tree[curr][0] + 1;
        }
        
        //Once the tree dictionary has been prepared, initialize the list of traversals for the method to return.
        List<List<int>> res = new List<List<int>>(); 
        
        //Then perform the traversal for each query and add the result to the return list.
        foreach (int q in queries) {
            res.Add(DFS(tree, 1, q));
        }
        
        //Once done, the result should include the in-order traversal results for every input query.
        return res;
    }
    
    public static List<int> DFS(Dictionary<int, int[]> tree, int curr, int q) {
        //First, initialize the list value to either return or add to during recursion.
        List<int> ret = new List<int>(); 
        
        //Then, check if the current node index is in the tree.
        if (tree.ContainsKey(curr)) {
            //If the current node exists, retrieve this node's children and check if a swap is needed.
            int l = tree[curr][1];
            int r = tree[curr][2];
            tree[curr][1] = tree[curr][0] % q == 0 ? r : l;
            tree[curr][2] = tree[curr][0] % q == 0 ? l : r;
            
            //Then perform the in-order traversal recursively.
            ret.AddRange(DFS(tree, tree[curr][1], q));
            ret.Add(curr);
            ret.AddRange(DFS(tree, tree[curr][2], q));
        }
        
        //By checking if the current node index exists in the tree, you don't have to worry about out-of-range access errors. Meeting the end condition returns  an empty list without further recursion.
        return ret;
    }

  • dcctexx
     + 0 comments

    Boring explanation, easy problem.

    Solution steps:

    1) create a binary tree with given indexes

    2) traverse it to set depths of each node (and store all nodes of depth d in a dictionary D)

    3) for each query q, iterate through D[q], D[2q], ..., until D stops containing the key, and swap the children of all nodes of each node list

    4) perform in-order traversal, as expected

  • jaspier
     + 0 comments

    The explanation for this problem is incredible hard, it complicates things without a reason, and the examples are confusing. It needs a lot of rewritting.

  • fantanoice
     + 0 comments

    I don't understand why the output is how it is:

    • It is recording the 'parent' node before we've finished traversing its right-hand children. How can we say we've traversed all its "subtrees" when we've ignored half of them?
    • Test Case 1 doesn't have the first traversed node in its output?

    (Using C++)