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:

Go to the source code of this file.

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
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.
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.
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.
Node *	operations_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.
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.
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.
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

Definition in file inorder_successor_of_bst.cpp.

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

root	Root node of the tree.

Returns

void

Definition at line 210 of file inorder_successor_of_bst.cpp.

                                {
    if (rootNode == nullptr) {
        return;
    }
    deallocate(rootNode->left);
    deallocate(rootNode->right);
    delete (rootNode);
}

findMinNode()

Node * operations_on_datastructures::inorder_traversal_of_bst::findMinNode

(

Node *

root

)

Finds and return the minimum node in BST.

Parameters

root	A pointer to root node.

Returns

Node* Pointer to the found node

Definition at line 121 of file inorder_successor_of_bst.cpp.

                              {
    if (root == nullptr) {
        return root;
    }
    while (root->left != nullptr) {
        root = root->left;
    }
    return root;
}

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

root	A pointer to the root node of the BST
data	The data (or the data of node) for which we have to find inorder successor.

Returns

Node pointer to the inorder successor node.

Definition at line 176 of file inorder_successor_of_bst.cpp.

                                                    {
    Node *current = getNode(root, data);
    if (current == nullptr) {
        return nullptr;
    }
 
    // Case - 1
    if (current->right != nullptr) {
        return findMinNode(current->right);
    }
    // case - 2
    else {
        Node *successor = nullptr;
        Node *ancestor = root;
 
        while (ancestor != current && ancestor != nullptr) {
            // This means my current node is in left of the root node
            if (current->data < ancestor->data) {
                successor = ancestor;
                ancestor = ancestor->left;  // keep going left
            } else {
                ancestor = ancestor->right;
            }
        }
        return successor;  // Nodes with maximum vales will not have a successor
    }
}

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

root	Pointer to the root node of the BST
data	Data 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.

Definition at line 100 of file inorder_successor_of_bst.cpp.

                                        {
    if (root == nullptr) {
        return nullptr;
    } else if (root->data == data) {
        return root;  
    } else if (data > root->data) {
        return getNode(root->right, data);
    } else {
        return getNode(root->left, data);
    }
}

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

root	Pointer to the root node of the BST
data	Data to be inserted.

Returns

Node* Pointer to the root node.

Definition at line 82 of file inorder_successor_of_bst.cpp.

                                       {
    if (root == nullptr) {
        root = makeNode(data);
    } else if (data <= root->data) {
        root->left = Insert(root->left, data);
    } else {
        root->right = Insert(root->right, data);
    }
    return root;
}

main()

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

Main function.

Parameters

argc	commandline argument count (ignored)
argv	commandline 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!

Definition at line 398 of file inorder_successor_of_bst.cpp.

                                 {
    test();  // run self-test implementations
 
    operations_on_datastructures::inorder_traversal_of_bst::Node *root =
        nullptr;  
    std::vector<int64_t> node_data{3,  4, 5,
                                   89, 1, 2};  
 
    int64_t targetElement = 4;  
    root = operations_on_datastructures::inorder_traversal_of_bst::makeBST(
        root, node_data);  
 
    operations_on_datastructures::inorder_traversal_of_bst::Node
        *inorderSuccessor = operations_on_datastructures::
            inorder_traversal_of_bst::getInorderSuccessor(root, targetElement);
 
    std::cout << "In-order sequence is : ";
    operations_on_datastructures::inorder_traversal_of_bst::printInorder(root);
    std::cout << std::endl;
 
    if (inorderSuccessor == nullptr) {
        std::cout << "Inorder successor for last node is NULL" << std::endl;
    } else {
        std::cout << "Target element is : " << targetElement << std::endl;
        std::cout << "Inorder successor for target element is : "
                  << inorderSuccessor->data << std::endl;
    }
 
    deallocate(root);  
 
    return 0;
}

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

root	Pointer to the root node.
data	A vector containing integer values which are suppose to be inserted as nodes in BST.

Returns

Node pointer to the root node.

Definition at line 155 of file inorder_successor_of_bst.cpp.

                                                          {
    for (int64_t values : data) {
        root = Insert(root, values);
    }
    return root;
}

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

data	Data 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

Definition at line 68 of file inorder_successor_of_bst.cpp.

                             {
    Node *node = new Node();
    node->data = data;      
    node->left = nullptr;   
    node->right = nullptr;  
    return node;
}

printInorder()

void operations_on_datastructures::inorder_traversal_of_bst::printInorder

(

Node *

root

)

Prints the BST in inorder traversal using recursion.

Parameters

root	A pointer to the root node of the BST.

Returns

void

recursive call to left subtree

recursive call to right subtree

Definition at line 136 of file inorder_successor_of_bst.cpp.

                              {
    if (root == nullptr) {
        return;
    }
 
    printInorder(root->left);  
    std::cout << root->data << " ";
    printInorder(root->right);  
}

test()

static void test ( )

static

Self-test implementations.

Returns

void

Definition at line 387 of file inorder_successor_of_bst.cpp.

                   {
    TestCases tc;
    tc.runTests();
}