online advertising

Sunday, November 27, 2016

HackerRank - Tree: Height of a Binary Tree

Problem:

Please find the problem here.

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

No comments :

Post a Comment