online advertising

Sunday, November 27, 2016

HackerRank - Swap Nodes [Algo]

Problem:

Please find the problem here.

Solution: 

Initially I thought about indexing the nodes by height to make it fast to find the nodes to swap. As a second thought, we need to output the in-order traversal, which take linear time anyway, we might as well swap-as-we-go during the in-order traversal!

Code:

#include "stdafx.h"

// https://www.hackerrank.com/challenges/swap-nodes-algo

#include "HACKER_RANK_SWAP_NODES_ALGO.h"
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

namespace _HACKER_RANK_SWAP_NODES_ALGO
{
    struct node
    {
        node* left;
        node* right;
        int data;
    };

    void inOrderSwapAndPrint(node* node, int k, int depth)
    {
        if (node == nullptr)
        {
            return;
        }
        if (depth % k == 0)
        {
            swap(node->left, node->right);
        }
        inOrderSwapAndPrint(node->left, k, depth + 1);
        cout << node->data << " ";
        inOrderSwapAndPrint(node->right, k, depth + 1);
    }

    int main()
    {
        int n;
        cin >> n;
        vector<node*> nodes(n);
        vector<bool> has_parent(n);
        for (int i = 0; i < n; i++)
        {
            nodes[i] = new node();
            nodes[i]->data = i + 1;
            nodes[i]->left = nullptr;
            nodes[i]->right = nullptr;
            has_parent[i] = false;
        }

        // Build the tree from input
        for (int i = 0; i < n; i++)
        {
            int a;
            int b;
            cin >> a;
            cin >> b;
            if (a != -1)
            {
                nodes[i]->left = nodes[a - 1];
                has_parent[a - 1] = true;
            }
            if (b != -1)
            {
                nodes[i]->right = nodes[b - 1];
                has_parent[b - 1] = true;
            }
        }

        // Finding the root
        node* root = nullptr;
        for (int i = 0; i < n; i++)
        {
            if (!has_parent[i])
            {
                if (root == nullptr)
                {
                    root = nodes[i];
                }
                else
                {
                    throw 1;
                }
            }
        }

        int t;
        cin >> t;
        for (int i = 0; i < t; i++)
        {
            int k;
            cin >> k;
            inOrderSwapAndPrint(root, k, 1);
        }
        cout << endl;

        return 0;
    }
};

int HACKER_RANK_SWAP_NODES_ALGO()
{
    _HACKER_RANK_SWAP_NODES_ALGO::main();
    return 0;
}

No comments :

Post a Comment