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, Binary Tree Inorder Traversal 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;
}
Inorder Traversal
In Inorder Traversal root node is visited in between it’s left and right child. For more information related to inorder successor visit Binary Tree Inorder Traversal Explanation.
Let’s look into an example to understand it better.
For the Binary tree mentioned in above image, Inorder traversal would be 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Inorder Successor of a Node
Inorder Successor of a Node in a binary tree is the node which is followed after the Node in Inorder Traversal of the Binary Tree.
In case, given node is the last Node of the Inorder Traversal then it’s successor will be NULL.
Let’s look into an algorithm to find an Inorder successor of a node.
Algorithm
- If no right child is present for a Node then that node will be the last node in Inorder Traversal and Hence it’s successor would be NULL. Return NULL in this case.
- If Right child is present then define a temp pointer pointing to right child of the node.
- While temp pointer is not null
- while left child of temp pointer is present
- set temp pointer to temp pointers left child.
- return temp pointer.
- while left child of temp pointer is present
Let’s look into the sample code for finding inorder successor of a node.
BinaryTree* find_inorder_successor (BinaryTree* root, BinaryTree* node)
{
if (!root)
{
return NULL;
}
if (!node)
{
return NULL;
}
if (node -> m_right)
{
BinaryTree* temp = node -> m_right;
while (temp -> m_left)
{
temp = temp -> m_left;
}
return temp;
}
else
{
return NULL;
}
}
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.
void check_inorder_successor_helper (BinaryTree* root, int searched_data)
{
BinaryTree* searched_node = search_node_in_binary_tree (root, searched_data);
if (searched_node)
{
BinaryTree* inorder_successor = find_inorder_successor (root, searched_node);
if (inorder_successor)
{
cout << "Inorder successor of " << searched_data << " is " << inorder_successor -> m_data << endl;
}
else
{
cout << "Inorder successor of " << searched_data << " is None" << endl;
}
}
}
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 << " Inorder Traversal: ";
inorder_traversal (root);
cout << endl;
check_inorder_successor_helper (root, 7);
check_inorder_successor_helper (root, 3);
check_inorder_successor_helper (root, 5);
check_inorder_successor_helper (root, 10);
}
Let’s analyze the output of this main function.
Binary tree contents: 5 3 2 1 4 7 6 9 8 10
Inorder Traversal: 1 2 3 4 5 6 7 8 9 10
Inorder successor of 7 is 8
Inorder successor of 3 is 4
Inorder successor of 5 is 6
Inorder successor of 10 is None
