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