Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
inorder_successor_of_bst.cpp File Reference

An implementation for finding the Inorder successor of a binary search tree Inorder successor of a node is the next node in Inorder traversal of the Binary Tree. Inorder Successor is NULL for the last node in Inorder traversal. More...

#include <cassert>
#include <iostream>
#include <vector>
Include dependency graph for inorder_successor_of_bst.cpp:

Classes

class  operations_on_datastructures::inorder_traversal_of_bst::Node
 A Node structure representing a single node in BST. More...
 
class  TestCases
 class encapsulating the necessary test cases More...
 

Namespaces

namespace  operations_on_datastructures
 for std::vector
 
namespace  inorder_successor_of_bst
 Functions for the Inorder successor of a binary search tree implementation.
 

Functions

Nodeoperations_on_datastructures::inorder_traversal_of_bst::makeNode (int64_t data)
 Allocates a new node in heap for given data and returns it's pointer.
 
Nodeoperations_on_datastructures::inorder_traversal_of_bst::Insert (Node *root, int64_t data)
 Inserts the given data in BST while maintaining the properties of BST.
 
Nodeoperations_on_datastructures::inorder_traversal_of_bst::getNode (Node *root, int64_t data)
 Searches the given data in BST and returns the pointer to the node containing that data.
 
Nodeoperations_on_datastructures::inorder_traversal_of_bst::findMinNode (Node *root)
 Finds and return the minimum node in BST.
 
void operations_on_datastructures::inorder_traversal_of_bst::printInorder (Node *root)
 Prints the BST in inorder traversal using recursion.
 
Nodeoperations_on_datastructures::inorder_traversal_of_bst::makeBST (Node *root, const std::vector< int64_t > &data)
 This function is used in test cases to quickly create BST containing large data instead of hard coding it in code. For a given root, this will add all the nodes containing data passes in data vector.
 
Nodeoperations_on_datastructures::inorder_traversal_of_bst::getInorderSuccessor (Node *root, int64_t data)
 Inorder successor of a node is the next node in inorder traversal of the Binary Tree. This function takes the root node and the data of the node for which we have to find the inorder successor, and returns the inorder successor node.
 
void operations_on_datastructures::inorder_traversal_of_bst::deallocate (Node *rootNode)
 This function clears the memory allocated to entire tree recursively. Its just for clean up the memory and not relevant to the actual topic.
 
static void test ()
 Self-test implementations.
 
int main (int argc, char *argv[])
 Main function.
 

Detailed Description

An implementation for finding the Inorder successor of a binary search tree Inorder successor of a node is the next node in Inorder traversal of the Binary Tree. Inorder Successor is NULL for the last node in Inorder traversal.

Case 1: The given node has the right node/subtree

 * In this case, the left-most deepest node in the right subtree will

come just after the given node as we go to left deep in inorder.

  • Go deep to left most node in right subtree. OR, we can also say in case if BST, find the minimum of the subtree for a given node.

Case 2: The given node does not have a right node/subtree

Method 1: Use parent pointer (store the address of parent nodes)

  • If a node does not have the right subtree, and we already visited the node itself, then the next node will be its parent node according to inorder traversal, and if we are going to parent from left, then the parent would be unvisited.
  • In other words, go to the nearest ancestor for which given node would be in left subtree.

Method 2: Search from the root node

  • In case if there is no link from a child node to the parent node, we need to walk down the tree starting from the root node to the given node, by doing so, we are visiting every ancestor of the given node.
  • In order successor would be the deepest node in this path for which given node is in left subtree.
Author
Nitin Sharma

Function Documentation

◆ deallocate()

void operations_on_datastructures::inorder_traversal_of_bst::deallocate ( Node * rootNode)

This function clears the memory allocated to entire tree recursively. Its just for clean up the memory and not relevant to the actual topic.

Parameters
rootRoot node of the tree.
Returns
void
210 {
211 if (rootNode == nullptr) {
212 return;
213 }
214 deallocate(rootNode->left);
215 deallocate(rootNode->right);
216 delete (rootNode);
217}
void deallocate(Node *rootNode)
This function clears the memory allocated to entire tree recursively. Its just for clean up the memor...
Definition inorder_successor_of_bst.cpp:210
Here is the call graph for this function:

◆ findMinNode()

Node * operations_on_datastructures::inorder_traversal_of_bst::findMinNode ( Node * root)

Finds and return the minimum node in BST.

Parameters
rootA pointer to root node.
Returns
Node* Pointer to the found node
121 {
122 if (root == nullptr) {
123 return root;
124 }
125 while (root->left != nullptr) {
126 root = root->left;
127 }
128 return root;
129}
Here is the call graph for this function:

◆ getInorderSuccessor()

Node * operations_on_datastructures::inorder_traversal_of_bst::getInorderSuccessor ( Node * root,
int64_t data )

Inorder successor of a node is the next node in inorder traversal of the Binary Tree. This function takes the root node and the data of the node for which we have to find the inorder successor, and returns the inorder successor node.

Search from the root node as we need to walk the tree starting from the root node to the given node, by doing so, we are visiting every ancestor of the given node. In order successor would be the deepest node in this path for which given node is in left subtree. Time complexity O(h)

Parameters
rootA pointer to the root node of the BST
dataThe data (or the data of node) for which we have to find inorder successor.
Returns
Node pointer to the inorder successor node.
176 {
177 Node *current = getNode(root, data);
178 if (current == nullptr) {
179 return nullptr;
180 }
181
182 // Case - 1
183 if (current->right != nullptr) {
184 return findMinNode(current->right);
185 }
186 // case - 2
187 else {
188 Node *successor = nullptr;
189 Node *ancestor = root;
190
191 while (ancestor != current && ancestor != nullptr) {
192 // This means my current node is in left of the root node
193 if (current->data < ancestor->data) {
194 successor = ancestor;
195 ancestor = ancestor->left; // keep going left
196 } else {
197 ancestor = ancestor->right;
198 }
199 }
200 return successor; // Nodes with maximum vales will not have a successor
201 }
202}
int data[MAX]
test data
Definition hash_search.cpp:24
Node * findMinNode(Node *root)
Finds and return the minimum node in BST.
Definition inorder_successor_of_bst.cpp:121
Node * getNode(Node *root, int64_t data)
Searches the given data in BST and returns the pointer to the node containing that data.
Definition inorder_successor_of_bst.cpp:100
Definition linkedlist_implentation_usingarray.cpp:14
Here is the call graph for this function:

◆ getNode()

Node * operations_on_datastructures::inorder_traversal_of_bst::getNode ( Node * root,
int64_t data )

Searches the given data in BST and returns the pointer to the node containing that data.

Parameters
rootPointer to the root node of the BST
dataData to be Searched.
Returns
Node* pointer to the found node

Node found!

Traverse right subtree recursively as the given data is greater than the data in root node, data must be present in right subtree.

Traverse left subtree recursively as the given data is less than the data in root node, data must be present in left subtree.

100 {
101 if (root == nullptr) {
102 return nullptr;
103 } else if (root->data == data) {
104 return root; /// Node found!
105 } else if (data > root->data) {
106 /// Traverse right subtree recursively as the given data is greater than
107 /// the data in root node, data must be present in right subtree.
108 return getNode(root->right, data);
109 } else {
110 /// Traverse left subtree recursively as the given data is less than the
111 /// data in root node, data must be present in left subtree.
112 return getNode(root->left, data);
113 }
114}
T data(T... args)
Here is the call graph for this function:

◆ Insert()

Node * operations_on_datastructures::inorder_traversal_of_bst::Insert ( Node * root,
int64_t data )

Inserts the given data in BST while maintaining the properties of BST.

Parameters
rootPointer to the root node of the BST
dataData to be inserted.
Returns
Node* Pointer to the root node.
82 {
83 if (root == nullptr) {
84 root = makeNode(data);
85 } else if (data <= root->data) {
86 root->left = Insert(root->left, data);
87 } else {
88 root->right = Insert(root->right, data);
89 }
90 return root;
91}
Node * makeNode(int64_t data)
Allocates a new node in heap for given data and returns it's pointer.
Definition inorder_successor_of_bst.cpp:68
Here is the call graph for this function:

◆ main()

int main ( int argc,
char * argv[] )

Main function.

Parameters
argccommandline argument count (ignored)
argvcommandline array of arguments (ignored)
Returns
0 on exit

< root node of the bst

< Data to add nodes in BST

< An element to find inorder successor for.

< Making BST

memory cleanup!

398 {
399 test(); // run self-test implementations
400
402 nullptr; ///< root node of the bst
403 std::vector<int64_t> node_data{3, 4, 5,
404 89, 1, 2}; ///< Data to add nodes in BST
405
406 int64_t targetElement = 4; ///< An element to find inorder successor for.
408 root, node_data); ///< Making BST
409
411 *inorderSuccessor = operations_on_datastructures::
412 inorder_traversal_of_bst::getInorderSuccessor(root, targetElement);
413
414 std::cout << "In-order sequence is : ";
417
418 if (inorderSuccessor == nullptr) {
419 std::cout << "Inorder successor for last node is NULL" << std::endl;
420 } else {
421 std::cout << "Target element is : " << targetElement << std::endl;
422 std::cout << "Inorder successor for target element is : "
423 << inorderSuccessor->data << std::endl;
424 }
425
426 deallocate(root); /// memory cleanup!
427
428 return 0;
429}
A Node structure representing a single node in BST.
Definition inorder_successor_of_bst.cpp:56
int64_t data
The key/value of the node.
Definition inorder_successor_of_bst.cpp:58
T endl(T... args)
Node * makeBST(Node *root, const std::vector< int64_t > &data)
This function is used in test cases to quickly create BST containing large data instead of hard codin...
Definition inorder_successor_of_bst.cpp:155
void printInorder(Node *root)
Prints the BST in inorder traversal using recursion.
Definition inorder_successor_of_bst.cpp:136
static void test()
Self-test implementations.
Definition inorder_successor_of_bst.cpp:387
Here is the call graph for this function:

◆ makeBST()

Node * operations_on_datastructures::inorder_traversal_of_bst::makeBST ( Node * root,
const std::vector< int64_t > & data )

This function is used in test cases to quickly create BST containing large data instead of hard coding it in code. For a given root, this will add all the nodes containing data passes in data vector.

Parameters
rootPointer to the root node.
dataA vector containing integer values which are suppose to be inserted as nodes in BST.
Returns
Node pointer to the root node.
155 {
156 for (int64_t values : data) {
157 root = Insert(root, values);
158 }
159 return root;
160}
Here is the call graph for this function:

◆ makeNode()

Node * operations_on_datastructures::inorder_traversal_of_bst::makeNode ( int64_t data)

Allocates a new node in heap for given data and returns it's pointer.

Parameters
dataData for the node.
Returns
A pointer to the newly allocated Node.

< setting data for node

< setting left child as null

< setting right child as null

68 {
69 Node *node = new Node();
70 node->data = data; ///< setting data for node
71 node->left = nullptr; ///< setting left child as null
72 node->right = nullptr; ///< setting right child as null
73 return node;
74}
struct node { int data; int height; struct node *left; struct node *right;} node
for std::queue
Definition avltree.cpp:13
Definition binary_search_tree.cpp:11
Here is the call graph for this function:

◆ printInorder()

void operations_on_datastructures::inorder_traversal_of_bst::printInorder ( Node * root)

Prints the BST in inorder traversal using recursion.

Parameters
rootA pointer to the root node of the BST.
Returns
void

recursive call to left subtree

recursive call to right subtree

136 {
137 if (root == nullptr) {
138 return;
139 }
140
141 printInorder(root->left); /// recursive call to left subtree
142 std::cout << root->data << " ";
143 printInorder(root->right); /// recursive call to right subtree
144}
Here is the call graph for this function:

◆ test()

static void test ( )
static

Self-test implementations.

Returns
void
387 {
388 TestCases tc;
389 tc.runTests();
390}
class encapsulating the necessary test cases
Definition inorder_successor_of_bst.cpp:225
void runTests()
Executes test cases.
Definition inorder_successor_of_bst.cpp:243
Here is the call graph for this function: