# Maximum element between two nodes of BST in c

C program for Maximum element between two nodes of BST. Here more solutions.

``````// Include header file
#include <stdio.h>
#include <stdlib.h>

// C program for
// Detect max nodes between given two nodes of a BST

// Binary Search Tree Node
typedef struct TreeNode
{
// Define useful field of TreeNode
// Data value
int data;
// Indicates left and right subtree
struct TreeNode * left;
struct TreeNode * right;
}TreeNode;
TreeNode * getTreeNode(int data)
{
// Create dynamic memory of TreeNode
TreeNode * ref = (TreeNode * ) malloc(sizeof(TreeNode));
if (ref == NULL)
{
// Failed to create memory
return NULL;
}
ref->data = data;
ref->left = NULL;
ref->right = NULL;
return ref;
}

typedef struct BinarySearchTree
{
// Define useful field of BinarySearchTree
struct TreeNode * root;
}BinarySearchTree;

BinarySearchTree * getBinarySearchTree()
{
// Create dynamic memory of BinarySearchTree
BinarySearchTree * ref = (BinarySearchTree * ) malloc(sizeof(BinarySearchTree));
if (ref == NULL)
{
// Failed to create memory
return NULL;
}
ref->root = NULL;
return ref;
}
// Insert a new node in BST
void addNode(BinarySearchTree * ref, int value)
{
// Create a dynamic node of binary search tree
TreeNode * node = getTreeNode(value);
if (ref->root == NULL)
{
// When adds a first node in binary tree
ref->root = node;
}
else
{
TreeNode * find = ref->root;
// Add new node to proper position
while (find != NULL)
{
if (find->data >= value)
{
if (find->left == NULL)
{
find->left = node;
return;
}
else
{
// Visit left sub-tree
find = find->left;
}
}
else
{
if (find->right == NULL)
{
find->right = node;
return;
}
else
{
// Visit right sub-tree
find = find->right;
}
}
}
}
}
TreeNode * findNode(TreeNode * node,
int value)
{
if (node != NULL)
{
if (node->data > value)
{
// Find node in left subtree
return findNode(node->left, value);
}
else if (node->data < value)
{
// Find node in right subtree
return findNode(node->right, value);
}
else
{
// When node exist
return node;
}
}
// When node is not exist
return NULL;
}
// Find LCA of two BST nodes
TreeNode * lca(TreeNode * node, int first, int second)
{
if (node != NULL)
{
if (node->data > first && node->data > second)
{
return lca(node->left, first, second);
}
else if (node->data < first && node->data < second)
{
return lca(node->right, first, second);
}
return node;
}
return NULL;
}
void findMaxBetween(BinarySearchTree * ref, int first, int second)
{
if (ref->root != NULL)
{
// First we are check that given node are exist or not in BST
if (findNode(ref->root, first) != NULL &&
findNode(ref->root, second) != NULL)
{
// If given element is exist then get LCA
TreeNode * node = lca(ref->root, first, second);
int find = first;
if (first < second)
{
find = second;
}
int result = find;
// node is lca of both node (x,y)
// so we consider path from node of largest of (x,y)
// And find max node of this path
while (node != NULL)
{
if (node->data > result)
{
result = node->data;
}
if (node->data > find)
{
// Visit to left child
node = node->left;
}
else if (node->data < find)
{
// Visit to right child
node = node->right;
}
else
{
break;
}
}
printf("Max Node Between [%d,%d] is %d\n",first,second, result);
}
else
{
printf("Node [%d,%d] are missing",first,second);
}
}
else
{
printf("\nEmpty BST");
}
}
int main()
{
BinarySearchTree * tree = getBinarySearchTree();
// Binary search tree
/*
10
/ \
/   \
/     \
3      19
/ \    /  \
1   4  14  50
/ \
-3   2

*/
// Testing
findMaxBetween(tree, 2, 14);
findMaxBetween(tree, -3, 4);
findMaxBetween(tree, 10, 2);
findMaxBetween(tree, 3, 2);
return 0;
}``````

Output

``````Max Node Between [2,14] is 19
Max Node Between [-3,4] is 4
Max Node Between [10,2] is 10
Max Node Between [3,2] is 3``````

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.