15 February 2018

Views: 5

/*Disable Third Party Ads

Question: TestDome - TreeHeight

Solution by Arash Partow 2014

A tree is an abstract data structure consisting of nodes. Each node

has only one parent node and zero or more child nodes. Each tree has

one special node, called a root, which has no parent node. A node is

called a leaf if it has no child nodes. The height of a tree is the

largest distance (number of parent-child connections) from the root to

a leaf.

Write a function that calculates the height of a given tree. For

example, the tree below has a height of 2 since the longest distance

(number of parent-child connections) from the root to a leaf is 2 (the

connections are the root to a node and then the node to leaf 1):

*/

#include <stdexcept>

#include <iostream>

#include

class TreeNode

{

public:

TreeNode(TreeNode* leftChild, TreeNode* rightChild)

{

this->leftChild = leftChild;

this->rightChild = rightChild;

}

TreeNode* getLeftChild() const

{

return this->leftChild;

}

TreeNode* getRightChild() const

{

return this->rightChild;

}

private:

TreeNode* leftChild;

TreeNode* rightChild;

};

class TreeHeight

{

public:

static int calculateHeight(const TreeNode& root)

{

return calculateHeightx(root);

}

private:

static int calculateHeightx(const TreeNode& root)

{

int hl = 0;

int hr = 0;

if (root.getLeftChild() != NULL)

hl = calculateHeightx(*root.getLeftChild()) + 1;

if (root.getRightChild() != NULL)

hr = calculateHeightx(*root.getRightChild()) + 1;

return std::max(hl,hr);

}

};

#ifndef RunTests

int main(int argc, const char* argv[])

{

TreeNode* leaf1 = new TreeNode(NULL, NULL);

TreeNode* leaf2 = new TreeNode(NULL, NULL);

TreeNode* node = new TreeNode(leaf1, NULL);

TreeNode* root = new TreeNode(node, leaf2);

std::cout TreeHeight::calculateHeight(*root);

}

#endif