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 Postorder 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;
}
Postorder Traversal
In Postorder Traversal root node is visited before it’s left and right child. For more information related to Postorder successor visit Binary Tree Postorder Traversal Explanation.
Let’s look into an example to understand it better.
For the Binary tree mentioned in above image, Postorder traversal would be 1 2 4 3 6 8 10 9 7 5.
Postorder Successor of a Node
Postorder Successor of a Node in a binary tree is the node which is followed after the Node in Postorder Traversal of the Binary Tree.
In case, given node is the last Node of the Postorder Traversal then it’s successor will be NULL.
Let’s look into an algorithm to find an Postorder successor of a node.
Algorithm
- Find parent node of the given node.
- If parent node is not present then return NULL.
- If given node is parent’s right child then return parent node.
- If given node is parent’s left child and parent’s right child is not present then return parent node.
- If parent’s right child is present then set temp pointer to parent’s right child.
- while temp pointer is present.
- if left child of temp is present then set temp pointer to left child.
- return temp pointer.
- while temp pointer is present.
Let’s look into the sample code for finding Postorder successor of a node.
BinaryTree* find_postorder_successor (BinaryTree* root, BinaryTree* node)
{
if (!root)
{
return NULL;
}
if (!node)
{
return NULL;
}
BinaryTree* parent_node = find_parent_node (root, node -> m_data);
if (!parent_node)
{
return NULL;
}
if (node == parent_node -> m_right)
{
return parent_node;
}
/* node is left child of the parent */
if (parent_node -> m_right)
{
BinaryTree* temp = parent_node -> m_right;
while (temp -> m_left)
{
temp = temp -> m_left;
}
return temp;
}
return parent_node;
}
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_postorder_successor_helper (BinaryTree* root, int searched_data)
{
BinaryTree* searched_node = search_node_in_binary_tree (root, searched_data);
if (searched_node)
{
BinaryTree* postorder_successor = find_postorder_successor (root, searched_node);
if (postorder_successor)
{
cout << "Postorder successor of " << searched_data << " is " << postorder_successor -> m_data << endl;
}
else
{
cout << "Postorder 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 << " Postorder Traversal: ";
postorder_traversal (root);
cout << endl;
check_postorder_successor_helper (root, 1);
check_postorder_successor_helper (root, 2);
check_postorder_successor_helper (root, 3);
check_postorder_successor_helper (root, 4);
check_postorder_successor_helper (root, 5);
check_postorder_successor_helper (root, 6);
check_postorder_successor_helper (root, 7);
check_postorder_successor_helper (root, 8);
check_postorder_successor_helper (root, 9);
check_postorder_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
Postorder Traversal: 1 2 4 3 6 8 10 9 7 5
Postorder successor of 1 is 2
Postorder successor of 2 is 4
Postorder successor of 3 is 6
Postorder successor of 4 is 3
Postorder successor of 5 is None
Postorder successor of 6 is 8
Postorder successor of 7 is 5
Postorder successor of 8 is 10
Postorder successor of 9 is 7
Postorder successor of 10 is 9
