by A tree is a data structure similar to Linked list in which each node points to multiple nodes instead of simply pointing to the next node. A tree is called Binary tree if each node in a tree has maximum of two nodes.
An empty tree is also a Binary tree. We can call the two children of each node as Left and Right child of a node. The node of the tree which has no parent is called the Root of the tree. Perhaps Binary tree is the most used tree data structure in the programming world. Before going ahead have a look into Binary Tree basics and Binary Tree implementation.
Let’s have a look on basic class definition for Binary Tree.
class BinaryTree
{
public:
int m_data;
BinaryTree* m_left;
BinaryTree* m_right;
BinaryTree (int data);
BinaryTree (int data, BinaryTree* left, BinaryTree* right);
~BinaryTree ();
};
void print_binary_tree (BinaryTree* root)
{
cout << " " << root -> m_data;
if (root -> m_left)
print_binary_tree (root -> m_left);
if (root -> m_right)
print_binary_tree (root -> m_right);
}
void print_tree (BinaryTree* root)
{
cout << "Binary tree contents: ";
print_binary_tree (root);
cout << endl;
}
Height of a Binary Tree
Height of a binary tree is defined as the largest number of the edges in a path from root node to any of the leaf nodes in the Binary Tree which means Height of the Binary Tree is actually the height of the root node.
Important points
- An Empty tree height is “-1” as it has 0 nodes.
- A Tree with only one node has height of “0” as the longest path from root to leaf note is “0”.
Let’s define an algorithm to find the height of a Binary Tree.
Algorithm
- If tree is empty return -1
- Using recursive function
- Find the height of the left subtree of the root node.
- Find the height of the right subtree of the root node.
- Return the max value “max” of (1 + left subtree height) or (1 + right subtree height)
- Final Height of the tree = max – 1
Let’s look into an example to understand it better.
As shown in above image height of left Binary tree is 3 and right Binary Tree is 2.
Let’s look into the sample code for finding maximum node value.
int get_maximum_height (BinaryTree* root)
{
if (!root)
return 0;
int level_left = 0;
int level_right = 0;
if (root -> m_left)
level_left = get_maximum_height (root -> m_left);
if (root -> m_right)
level_right = get_maximum_height (root -> m_right);
return (level_right > level_left ? (1 + level_right) : (1 + level_left));
}
int get_height (BinaryTree* root)
{
return (get_maximum_height (root) - 1);
}
Few of the functions used below are explained in Binary Tree Implementation. Refer those before going ahead.
Let’s define a main function to use above functions.
int main ()
{
BinaryTree* node1 = new BinaryTree (1);
BinaryTree* node2 = new BinaryTree (2);
BinaryTree* node3 = new BinaryTree (3);
BinaryTree* node4 = new BinaryTree (4);
BinaryTree* node5 = new BinaryTree (5);
BinaryTree* node6 = new BinaryTree (6);
BinaryTree* node7 = new BinaryTree (7);
BinaryTree* node8 = new BinaryTree (8);
BinaryTree* node9 = new BinaryTree (9);
BinaryTree* node10 = new BinaryTree (10);
/* Set node5 as root node */
BinaryTree* root = node5;
node5 -> m_left = node3;
node3 -> m_left = node2;
node3 -> m_right = node4;
node2 -> m_left = node1;
node5 -> m_right = node7;
node7 -> m_left = node6;
node7 -> m_right = node9;
node9 -> m_right = node10;
node9 -> m_left = node8;
print_tree (root);
cout << "Height of Binary Tree: " << get_height (root) << endl;
delete_all_nodes (root);
}
Let’s analyze the output of this main function.
Binary tree contents: 5 3 2 1 4 7 6 9 8 10
Height of Binary Tree: 3
