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;
}
Find Maximum node value in a Binary Tree
Here we need to find out the maximum node value present in a Binary Tree. We are going to solve this problem using recursion. The idea is to find the maximum node value between root node, it’s left subtree and right subtree.
Let’s look into the algorithm to find maximum node value.
Algorithm
- Start from Root node.
- If root node is null then return.
- Call the recursive function with root left child and save function return value as max_left.
- Call the recursive function with root right child and save function return value as max_right.
- Compare root, max_left and max_right and return the maximum value which will be the maximum node value in a binary tree.
Let’s look into an example to understand it better.
For the Binary tree mentioned in above image, Maximum value is 10.
Let’s look into the sample code for finding maximum node value.
BinaryTree* get_maximum (BinaryTree* root)
{
if (!root)
return NULL;
BinaryTree* max = root;
BinaryTree* max_left = get_maximum (root -> m_left);
BinaryTree* max_right = get_maximum (root -> m_right);
if (max_left)
{
if (max_left -> m_data > max -> m_data)
{
max = max_left;
}
}
if (max_right)
{
if (max_right -> m_data > max -> m_data)
{
max = max_right;
}
}
return max;
}
Find Minimum node value in a Binary Tree
Here we need to find out the minimum node value present in a Binary Tree. We are going to solve this problem using recursion. The idea is to find the minimum node value between root node, it’s left subtree and right subtree.
Let’s look into the algorithm to find minimum node value.
Algorithm
- Start from Root node.
- If root node is null then return.
- Call the recursive function with root left child and save function return value as min_left.
- Call the recursive function with root right child and save function return value as min_right.
- Compare root, min_left and min_right and return the minimum value which will be the minimum node value in a binary tree.
For the Binary tree mentioned in above image, Minimum value is 1.
Let’s look into the sample code for finding minimum node value.
BinaryTree* get_minimum (BinaryTree* root)
{
if (!root)
return NULL;
BinaryTree* min = root;
BinaryTree* min_left = get_minimum (root -> m_left);
BinaryTree* min_right = get_minimum (root -> m_right);
if (min_left)
{
if (min_left -> m_data < min -> m_data)
{
min = min_left;
}
}
if (min_right)
{
if (min_right -> m_data < min -> m_data)
{
min = min_right;
}
}
return min;
}
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* root = new BinaryTree(20);
insert_after_certain_element (root, 10, 20);
insert_after_certain_element (root, 30, 20);
insert_after_certain_element (root, 40, 20);
insert_after_certain_element (root, 1, 40);
insert_after_certain_element (root, 50, 30);
insert_after_certain_element (root, 60, 20);
print_tree (root);
BinaryTree* max = get_maximum (root);
if (max)
{
cout << "Maximum node value: " << max -> m_data << endl;
}
else
{
cout << "Binary tree is empty" << endl;
}
BinaryTree* min = get_minimum (root);
if (min)
{
cout << "Minimum node value: " << min -> m_data << endl;
}
else
{
cout << "Binary tree is empty" << endl;
}
delete_all_nodes (root);
}
Let’s analyze the output of this main function.
Binary tree contents: 20 10 40 1 60 30 50
Maximum node value: 60
Minimum node value: 1
