Share

Question: TestDome - TreeHeight

Public

15 February 2018

Views: 40

/*
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

Advertisement

Disable Third Party Ads