Find the Maximum Element Between the Two Nodes of BST

Approach

We will use a two-step process to find the maximum element.
a.) Find the LCA of the two nodes.

b.) Find the maximum element between the LCA and the greater of X and Y values.

Let’s see the algorithm:

Algorithm

1. Find the LCA of X and Y.
2. Initialise a variable MAX by -1 if no element exists in the path from X to Y.
3. Traverse the tree from LCA to X and keep updating the MAX such that if the current value is greater than ‘MAX,’ the current value will become ‘MAX.’
4. Similarly, traverse the tree from LCA to Y and keep updating the ‘MAX.’
5. Return the ‘MAX.’
    

To Find LCA

1. Create a recursive function that requires the BST's root and X and Y values.
2. Begin with the root node.
3. Compare the current node's value to the nodes X and Y values.
   • If value(current node) < value(Node X & Y), X and Y lies in right subtree. We will call the recursive function for the right subtree.
   • If value(current node) > value(Node X & Y), X and Y lies in left subtree. We will call the recursive function for the left subtree.
   • If the above cases are false, return the current node value as LCA.

Implementation

This is the C++ code for our algorithm.

#include <bits/stdc++.h>
using namespace std;
struct node {
   int data;
   struct node* left;
   struct node* right;
};


//Creating a new node.
node *createNode(int i) {
   node *r = new node();
   r -> data = i;
   r -> left = NULL;
   r -> right = NULL;
   return r;
}


// Function to insert nodes in BST.
void InsertNode(struct node *root, int n) {
   node *p = root, *q = NULL;
   while (p != NULL) {
      q = p;
      if (p -> data < n) {
         p = p -> right;
      } else {
         p = p -> left;
      }
   }
   if (q == NULL) {
      p = createNode(n);
   } else {
      if (q -> data < n) {
         q -> right = createNode(n); } else {
            q -> left = createNode(n);
      }
   }
}


//Function to return maximum element.
int MaxElementInPath(node *q, int i) {
   node *p = q;
   int MAX = -1;


//Returning maximum value.
   while (p -> data != i) {
      if (p -> data > i) {
         MAX = max(MAX, p -> data);
         p = p -> left;
      } else {
         MAX = max(MAX, p -> data);
         p = p -> right;
      }
   }
   return max(MAX, i);
}


//MAximum element between two nodes.
int MaxElement(struct node *root, int x, int y) {
   node *r = root;


//Finding the LCA of nodes x and y.
   while ((x < r -> data && y < r -> data) || (x > r ->
   data && y > r -> data)) {
      if (x < r -> data && y < r -> data) {
         r = r -> left;
      } else if (x > r -> data && y > r -> data) {
         r = r -> right;
      }
   }
   return max(MaxElementInPath(r, x), MaxElementInPath(r, y));
}
int main() {
   int A[] = {25, 32, 23, 14, 28, 36, 10, 18}; int a = 18, b = 28;
   int n = sizeof(A) / sizeof(A[0]);
   struct node *root = createNode(A[0]);
   for (int i = 1; i < n; i++) InsertNode(root, A[i]);
   cout << "Maximum element between given nodes= " << MaxElement(root, a, b) << endl;
   return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output: 

Maximum element between given nodes= 32

You can also try this code with Online C++ Compiler

Run Code

Complexity Analysis

Time Complexity: The time complexity of this algorithm is O(h), where h is the tree's height. Since we are traversing the tree to find the maxim element. The complexity of traversing a BST is O(h).

Space Complexity: The space complexity is O(n), where n is the no of nodes. This complexity is due to the extra space required to create and store the BST.

Frequently Asked Questions

What is LCA?

LCA stands for Lowest Common Ancestor. In a rooted tree, the lowest (deepest) node that is an ancestor of both x and y is known as the LCA of the two nodes, x and y. An ancestor of node x can be any node on the path from the root to node x in a rooted tree. It also includes the node x value itself.

How to perform search operations in BST?

Search from the root node whenever an element has to be searched. Search for the element in the left subtree if the data is smaller than the key value. If not, look for the element in the right subtree. For every node, use the same algorithm.

What is the benefit of a binary search tree?

A binary search tree is a data structure that offers an effective way to iterate elements while providing quick insertion, removal, and lookup properties. We can always keep the cost of these functions O(log n). It is very effective and easy to implement.

Conclusion

We ran through the solution of finding maximum elements between two nodes in a BST. We hope this blog helped you.

This article is related to the binary search tree, so it is recommended to visit our curated section of BST at the Coding Ninjas Studio library, where you can learn:

• Construct BST from the given pre-order Traversal.
• Implementing Forward Iterator in BST.
• Insertion in Binary Search Tree.
• Deletion in Binary Search Tree and many more.

You can also visit our curated sections of AVL tree, Graph, Trie, Dynamic programming, and many more.

Here are some of the widespread binary tree problems for your coding practice:

• Size of largest BST in a Binary Tree.
• Partial BST.
• Merge Two BSTs.
• Time to Burn Tree.
• Optimal BST and many more at Coding Ninjas Studio.
   

If you liked our article, do upvote our article and help other ninjas grow.  You can refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, System Design, and many more!

Head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences and interview bundles, follow guided paths for placement preparations, and much more!!

We wish you Good Luck! Keep coding and keep reading Ninja!!