## Sunday, November 27, 2016

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