 2/4/2018 - 3:36 AM

## Get Edges and Height of a Binary Tree

``````// https://www.jdoodle.com/online-compiler-c++

#include <iostream>
#include <cstddef>
#include <queue>
#include <vector>

using namespace std;

class Node{
public:
int data;
Node *left;
Node *right;
Node(int d){
data = d;
left = NULL;
right = NULL;
}
};
class Solution{
public:
Node* insert(Node* root, int data) {
if(root == NULL) {
return new Node(data);
}
else {
Node* cur;
if(data <= root->data){
cur = insert(root->left, data);
root->left = cur;
}
else{
cur = insert(root->right, data);
root->right = cur;
}

return root;
}
}
int getHeight(Node* root){
// we will read each level of the tree if all nodes are null then we have reached maximum height

// if tree is empty return 0
if (root == NULL || (!root->left && !root->right))
{
return 0;
}

// create a queue and add the root node to it
queue<Node *> treeNodeQueue;
treeNodeQueue.push(root);

int heightCount = 0;
bool complete = false;

while (!complete)
{
// nodeCount indicates how many nodes there are at the current height (e.g. there is 1 node at the root height, the next level could have 0,1 or 2 nodes...)
int nodeCount = treeNodeQueue.size();

//
if (nodeCount == 0)
{
// there are no nodes at this level so it is the end of the tree.
complete = true;
break;
}

// we have traversed one height level
heightCount++;

// continue as long as there is a node remaining to be processed at this level
while (nodeCount > 0)
{
// get the current node
Node *node = treeNodeQueue.front();

// we start processing the current node
treeNodeQueue.pop();

if (node->left != NULL)
{
// add the left child node
treeNodeQueue.push(node->left);
}

if (node->right != NULL)
{
// add the right child node
treeNodeQueue.push(node->right);
}

// node has been processed so lower the count
nodeCount--;
}
}

// we -1 because we are counting the number of edges e.g. the root node is level 0.
return heightCount -1;
}
}; //End of Solution

int main() {
Solution myTree;
Node *root = NULL;
int t = 0;
int count = 0;
int data;
vector<int> nodelist;

t = 7;
nodelist = {3, 5, 2, 1, 4, 6, 7};

while(t-- > 0)
{
data = nodelist[count];
root = myTree.insert(root, data);
count++;
}
int height = myTree.getHeight(root);
cout << height;

return 0;
}``````