## Sunday, November 27, 2016

### HackerRank - Is This a Binary Search Tree?

Problem:

Solution:

To test if a given tree is a binary search tree, we simply do an in-order traversal and test if the value comes in order.

Slightly annoyed by the fact that the author re-defined binary search tree to not have duplicated values.

Analysis:

Suppose there exists an algorithm that solve the problem without reading all the nodes, an adversary can choose to give that node a value that doesn't fit the requirement of a binary search tree, therefore we need at least linear time, showing our algorithm is asymptotically optimal.

Code：

#include "stdafx.h"

// https://www.hackerrank.com/challenges/is-binary-search-tree

#include "HACKER_RANK_IS_BINARY_SEARCH_TREE.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _HACKER_RANK_IS_BINARY_SEARCH_TREE
{
struct Node
{
int data;
Node* left;
Node* right;
};

bool has_last = false;
int last = 10086;

bool checkBST(Node* root)
{
if (root == nullptr)
{
return true;
}
if (!checkBST(root->left)) { return false; }
if (has_last)
{
if (root->data < last)
{
return false;
}
}
else
{
has_last = true;
}
last = root->data;
if (!checkBST(root->right)) { return false; }
return true;
}
};

using namespace _HACKER_RANK_IS_BINARY_SEARCH_TREE;

int HACKER_RANK_IS_BINARY_SEARCH_TREE()
{
Node a;
Node b;
Node c;
Node d;
Node e;
Node f;
a.data = 3;
b.data = 5;
c.data = 2;
d.data = 1;
e.data = 4;
f.data = 6;
a.left = &b;
a.right = &c;
b.left = &d;
b.right = &e;
c.left = &f;
c.right = nullptr;
d.left = nullptr;
d.right = nullptr;
e.left = nullptr;
e.right = nullptr;
f.left = nullptr;
f.right = nullptr;
cout << checkBST(&a) << endl;
return 0;
}

### HackerRank - Swap Nodes [Algo]

Problem:

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

### HackerRank - Binary Search Tree : Lowest Common Ancestor

Problem:

Solution:

The fact that the input is a binary search tree guides the path, and we report once the path diverges!

It appears that when v1 is a ancestor of v2, then the least common ancestor is defined to be v1. This is not clear from the problem statement.

Code：

#include "stdafx.h"

// https://www.hackerrank.com/challenges/binary-search-tree-lowest-common-ancestor

#include "HACKER_RANK_BINARY_SEARCH_TREE_LOWEST_COMMON_ANCESTOR.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _HACKER_RANK_BINARY_SEARCH_TREE_LOWEST_COMMON_ANCESTOR
{
typedef struct node
{
int data;
node * left;
node * right;
} node;

node * lca(node * root, int v1, int v2)
{
if (v1 > v2)
{
return lca(root, v2, v1);
}
if (root == nullptr)
{
return nullptr;
}
if (v1 == root->data || v2 == root->data)
{
return root;
}
if (v1 < root->data && v2 > root->data)
{
return root;
}
else if (v1 < root->data && v2 < root->data)
{
return lca(root->left, v1, v2);
}
else
{
return lca(root->right, v1, v2);
}
}
};

using namespace _HACKER_RANK_BINARY_SEARCH_TREE_LOWEST_COMMON_ANCESTOR;

int HACKER_RANK_BINARY_SEARCH_TREE_LOWEST_COMMON_ANCESTOR()
{
node a;
node b;
node c;
node d;
node e;
node f;
a.data = 4;
b.data = 2;
c.data = 7;
d.data = 1;
e.data = 3;
f.data = 6;
a.left = &b;
a.right = &c;
b.left = &d;
b.right = &e;
c.left = &f;
c.right = nullptr;
d.left = nullptr;
d.right = nullptr;
e.left = nullptr;
e.right = nullptr;
f.left = nullptr;
f.right = nullptr;
cout << lca(&a, 1, 7)->data << endl;
return 0;
}

### HackerRank - Tree: Huffman Decoding

Problem:

Solution:

Just walk the tree as requested, and output a symbol when we reach a leaf node.

Code：

#include "stdafx.h"

// https://www.hackerrank.com/challenges/tree-huffman-decoding

#include "HACKER_RANK_TREE_HUFFMAN_DECODING.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _HACKER_RANK_TREE_HUFFMAN_DECODING
{
typedef struct node
{
int freq;
char data;
node * left;
node * right;

} node;

void decode_huff(node * root, string s)
{
node* cur = root;
for (size_t i = 0; i < s.length(); i++)
{
if (s[i] == '0')
{
cur = cur->left;
if (cur->left == nullptr && cur->right == nullptr)
{
cout << cur->data;
cur = root;
}
}
else
{
cur = cur->right;
if (cur->left == nullptr && cur->right == nullptr)
{
cout << cur->data;
cur = root;
}
}
}
}
};

using namespace _HACKER_RANK_TREE_HUFFMAN_DECODING;

int HACKER_RANK_TREE_HUFFMAN_DECODING()
{
node a;
node b;
node c;
node d;
node e;
a.data = '\0';
b.data = '\0';
c.data = 'A';
d.data = 'B';
e.data = 'C';
a.left = &b;
a.right = &c;
b.left = &d;
b.right = &e;
c.left = nullptr;
c.right = nullptr;
d.left = nullptr;
d.right = nullptr;
e.left = nullptr;
e.right = nullptr;
decode_huff(&a, "1001011");
return 0;
}

### HackerRank - Binary Search Tree : Insertion

Problem:

Solution:

Note the recursive solution - the given function prototype basically asked for it!

Code：

#include "stdafx.h"

// https://www.hackerrank.com/challenges/binary-search-tree-insertion

#include "HACKER_RANK_BINARY_SEARCH_TREE_INSERTION.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _HACKER_RANK_BINARY_SEARCH_TREE_INSERTION
{
typedef struct node
{
int data;
node * left;
node * right;
} node;

node * insert(node * root, int value)
{
if (root == nullptr)
{
node* new_node = new node();
new_node->data = value;
new_node->left = nullptr;
new_node->right = nullptr;
return new_node;
}
else
{
if (value < root->data)
{
root->left = insert(root->left, value);
}
else
{
root->right = insert(root->right, value);
}
return root;
}
}
};

using namespace _HACKER_RANK_BINARY_SEARCH_TREE_INSERTION;

int HACKER_RANK_BINARY_SEARCH_TREE_INSERTION()
{
node a;
node b;
node c;
node d;
node e;
a.data = 4;
b.data = 2;
c.data = 7;
d.data = 1;
e.data = 3;
a.left = &b;
a.right = &c;
b.left = &d;
b.right = &e;
c.left = nullptr;
c.right = nullptr;
d.left = nullptr;
d.right = nullptr;
e.left = nullptr;
e.right = nullptr;
node* f = insert(&a, 6);
cout << f->right->left->data << endl;
return 0;
}

### HackerRank - Tree: Level Order Traversal

Problem:

Solution:

The first level is simply the root, easy.
When we produce the first level, we produce the second level by enqueuing the left and right.
When we produce the second level output, we produce the third level, and so on.

One thing worth pointing out is the re-use of the same vector object, I am hoping that it can reuse some spaces so we are not doing allocations. The problem is that I wanted to use the indexing operator, that can be cumbersome with pointers, but c++ reference cannot be changed once initialized. The code I wrote used a mixture of pointer and reference to make this possible, basically, make the reference initialization happen after the swap every iteration.

Code：

#include "stdafx.h"

// https://www.hackerrank.com/challenges/tree-level-order-traversal

#include "HACKER_RANK_TREE_LEVEL_ORDER_TRAVERSAL.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

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

void LevelOrder(node * root)
{
vector<node*> buffer1;
vector<node*> buffer2;
vector<node*>* pBuffer1 = &buffer1;
vector<node*>* pBuffer2 = &buffer2;
buffer1.push_back(root);
while (true)
{
vector<node*>& prev_layer = *pBuffer1;
vector<node*>& next_layer = *pBuffer2;
if (prev_layer.size() == 0)
{
break;
}
for (int i = 0; i < prev_layer.size(); i++)
{
node* prev_node = prev_layer[i];
cout << prev_node->data << " ";
if (prev_node->left != nullptr)
{
next_layer.push_back(prev_node->left);
}
if (prev_node->right != nullptr)
{
next_layer.push_back(prev_node->right);
}
}
prev_layer.clear();
swap(pBuffer1, pBuffer2);
}
}
};

using namespace _HACKER_RANK_TREE_LEVEL_ORDER_TRAVERSAL;

int HACKER_RANK_TREE_LEVEL_ORDER_TRAVERSAL()
{
node a;
node b;
node c;
node d;
node e;
node f;
a.data = 3;
b.data = 5;
c.data = 2;
d.data = 1;
e.data = 4;
f.data = 6;
a.left = &b;
a.right = &c;
b.left = &d;
b.right = &e;
c.left = &f;
c.right = nullptr;
d.left = nullptr;
d.right = nullptr;
e.left = nullptr;
e.right = nullptr;
f.left = nullptr;
f.right = nullptr;
LevelOrder(&a);
return 0;
}

### HackerRank - Tree : Top View

Problem:

Solution:

The top view is basically the left chain and the right chain, they are obviously visible, and whenever they go in different direction, they are no longer visible.

To produce the left chain, I used recursion call stack the reverse the printing order so that we start with the leftmost node to the root, for the right chain, a simple loop suffice.

Code：

#include "stdafx.h"

// https://www.hackerrank.com/challenges/tree-top-view

#include "HACKER_RANK_TREE_TOP_VIEW.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

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

void left_chain(node* root)
{
if (root == nullptr)
{
return;
}
left_chain(root->left);
cout << root->data << " ";
}

void top_view(node * root)
{
left_chain(root);
node* cur = root;
while (cur != nullptr)
{
if (cur != root)
{
cout << cur->data << " ";
}
cur = cur->right;
}
}

};

using namespace _HACKER_RANK_TREE_TOP_VIEW;

int HACKER_RANK_TREE_TOP_VIEW()
{
node a;
node b;
node c;
node d;
node e;
node f;
node g;
node h;
node i;
a.data = 3;
b.data = 5;
c.data = 2;
d.data = 1;
e.data = 4;
f.data = 6;
g.data = 7;
h.data = 9;
i.data = 8;
a.left = &b;
a.right = &c;
b.left = &d;
b.right = &e;
c.left = &f;
c.right = &g;
d.left = nullptr;
d.right = &h;
e.left = nullptr;
e.right = nullptr;
f.left = nullptr;
f.right = nullptr;
g.left = &i;
g.right = nullptr;
h.left = nullptr;
h.right = nullptr;
i.left = nullptr;
i.right = nullptr;
top_view(&a);
return 0;
}

### HackerRank - Tree: Height of a Binary Tree

Problem:

Solution:

The interesting thing here is that we are counting the number of edges, not the number of nodes. Therefore we need to return -1 for the root node to make sure we subtract 1 from the final number of nodes. (number of edges = number of nodes - 1 on a path)

The interesting side-effect of this is that null will have a height of -1, and the judge seems to be fine with that.

Code：

#include "stdafx.h"

// https://www.hackerrank.com/challenges/tree-height-of-a-binary-tree

#include "HACKER_RANK_TREE_HEIGHT_OF_A_BINARY_TREE.h"
#include <iostream>
#include <algorithm>

using namespace std;

namespace _HACKER_RANK_TREE_HEIGHT_OF_A_BINARY_TREE
{
class Node
{
public:
int data;
Node* left;
Node* right;
};

int getHeight(Node* root)
{
if (root == nullptr)
{
return -1;
}
else
{
return 1 + max(getHeight(root->left), getHeight(root->right));
}
}
};

using namespace _HACKER_RANK_TREE_HEIGHT_OF_A_BINARY_TREE;

int HACKER_RANK_TREE_HEIGHT_OF_A_BINARY_TREE()
{
Node a;
Node b;
Node c;
Node d;
Node e;
Node f;
Node g;

a.data = 3;
b.data = 2;
c.data = 5;
d.data = 1;
e.data = 4;
f.data = 6;
g.data = 7;

a.left = &b;;
a.right = &c;
b.left = &d;
b.right = nullptr;
c.left = &e;
c.right = &f;
d.left = nullptr;
d.right = nullptr;
e.left = nullptr;
e.right = nullptr;
f.left = nullptr;
f.right = &g;
g.left = nullptr;
g.right = nullptr;
cout << getHeight(&a) << endl;
return 0;
}