Given a binary search tree and a target value, the task is to find the next greater element of the target value in the binary search tree.
Examples:
Input:
5
/ \
3 7
/ \ / \
2 4 6 8Target: 4
Output: 5
Explanation: The next greater element of 4 is 5Input:
4
/ \
2 6
/ \ \
1 3 8Target: 6
Output: 8
Explanation: The next greater element of 6 is 8
Approach: To solve the problem follow the below idea:
Finding the next greater element in a binary search tree involves performing an in-order traversal of the tree to create a sorted list of its node values. Once we have the sorted list of node values, we can easily find the next greater element of a given node by iterating through the list starting from the target node’s value until we find a value greater than the node’s value.
Below are the steps for the above approach:
- Perform an in-order traversal of the binary search tree and store its node values in a vector.
- Find the target node’s value in the vector.
- Iterate through the vector starting from the target node’s value until we find a value greater than the target node’s value.
- If we find a value greater than the target node’s value, return it as the next greater element. If we reach the end of the vector without finding a greater value, return -1 to indicate that the next greater element does not exist.
Below is the code for the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Definition for a binary// search tree node.struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(NULL), right(NULL) { }};void inorderTraversal(TreeNode* root, vector<int>& values){ if (!root) return; inorderTraversal(root->left, values); values.push_back(root->val); inorderTraversal(root->right, values);}int getNextGreaterElement(TreeNode* root, int target){ // To store the values of the binary // search tree vector<int> values; // Perform in-order traversal and // store values in the vector inorderTraversal(root, values); auto it // Find target value in the vector = find(values.begin(), values.end(), target); // If target value is not found, return // -1 if (it == values.end()) return -1; // Calculate the distance between the target // value and the beginning of the vector auto dist = distance(values.begin(), it); // Iterate over the vector starting // from the target value for (int i = dist + 1; i < values.size(); i++) { // If an element greater than the // target value is found, return it if (values[i] > target) { return values[i]; } } // If next greater element is not found, // return -1 return -1;}// Drivers codeint main(){ /* * 5 * / \ * 3 7 * / \ / \ * 2 4 6 8 */ TreeNode* root = new TreeNode(5); root->left = new TreeNode(3); root->right = new TreeNode(7); root->left->left = new TreeNode(2); root->left->right = new TreeNode(4); root->right->left = new TreeNode(6); root->right->right = new TreeNode(8); int target = 4; int nextGreaterElement = getNextGreaterElement(root, target); // Function Call cout << "The next greater element of " << target << " is " << nextGreaterElement << endl; return 0;} |
Java
// Java code for the above approach:import java.util.*;// Definition for a binary// search tree node.class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; left = null; right = null; }}public class Main { static void inorderTraversal(TreeNode root, List<Integer> values) { if (root == null) return; inorderTraversal(root.left, values); values.add(root.val); inorderTraversal(root.right, values); } static int getNextGreaterElement(TreeNode root, int target) { // To store the values of the binary // search tree List<Integer> values = new ArrayList<>(); // Perform in-order traversal and // store values in the list inorderTraversal(root, values); // Find target value in the list int dist = values.indexOf(target); // If target value is not found, return -1 if (dist == -1) return -1; // Iterate over the list starting // from the target value for (int i = dist + 1; i < values.size(); i++) { // If an element greater than the // target value is found, return it if (values.get(i) > target) { return values.get(i); } } // If next greater element is not found, // return -1 return -1; } // Drivers code public static void main(String[] args) { /* * 5 * / \ * 3 7 * / \ / \ * 2 4 6 8 */ TreeNode root = new TreeNode(5); root.left = new TreeNode(3); root.right = new TreeNode(7); root.left.left = new TreeNode(2); root.left.right = new TreeNode(4); root.right.left = new TreeNode(6); root.right.right = new TreeNode(8); int target = 4; int nextGreaterElement = getNextGreaterElement(root, target); // Function Call System.out.println("The next greater element of " + target + " is " + nextGreaterElement); }}// This code is contributed by Prajwal Kandekar |
Python3
# Definition for a binary search tree nodeclass TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right# Function to perform in-order traversal and store values in the vectordef inorderTraversal(root, values): if not root: return inorderTraversal(root.left, values) values.append(root.val) inorderTraversal(root.right, values)# Function to get the next greater element of a target in the binary search treedef getNextGreaterElement(root, target): # To store the values of the binary search tree values = [] # Perform in-order traversal and store values in the vector inorderTraversal(root, values) # Find target value in the vector try: index = values.index(target) except ValueError: return -1 # Iterate over the vector starting from the target value for i in range(index + 1, len(values)): # If an element greater than the target value is found, return it if values[i] > target: return values[i] # If next greater element is not found, return -1 return -1# Driver codeif __name__ == '__main__': # Construct the binary search tree """ 5 / \ 3 7 / \ / \ 2 4 6 8 """ root = TreeNode(5) root.left = TreeNode(3) root.right = TreeNode(7) root.left.left = TreeNode(2) root.left.right = TreeNode(4) root.right.left = TreeNode(6) root.right.right = TreeNode(8) # Target element to find the next greater element of target = 4 # Function call nextGreaterElement = getNextGreaterElement(root, target) # Print the result if nextGreaterElement == -1: print(f"The next greater element of {target} is not found.") else: print(f"The next greater element of {target} is {nextGreaterElement}.") |
C#
// C# code for the above approach:using System;using System.Collections.Generic;// Definition for a binary search tree node.class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; left = null; right = null; }}public class GFG { static void inorderTraversal(TreeNode root, List<int> values) { if (root == null) return; inorderTraversal(root.left, values); values.Add(root.val); inorderTraversal(root.right, values); } static int getNextGreaterElement(TreeNode root, int target) { // To store the values of the binary search tree List<int> values = new List<int>(); // Perform in-order traversal and store values in // the list inorderTraversal(root, values); // Find target value in the list int dist = values.IndexOf(target); // If target value is not found, return -1 if (dist == -1) return -1; // Iterate over the list starting from the target // value for (int i = dist + 1; i < values.Count; i++) { // If an element greater than the target value // is found, return it if (values[i] > target) { return values[i]; } } // If next greater element is not found, return -1 return -1; } static public void Main() { /* * 5 * / \ * 3 7 * / \ / \ * 2 4 6 8 */ TreeNode root = new TreeNode(5); root.left = new TreeNode(3); root.right = new TreeNode(7); root.left.left = new TreeNode(2); root.left.right = new TreeNode(4); root.right.left = new TreeNode(6); root.right.right = new TreeNode(8); int target = 4; int nextGreaterElement = getNextGreaterElement(root, target); // Function Call Console.WriteLine("The next greater element of " + target + " is " + nextGreaterElement); }}// This code is contributed by lokesh. |
Javascript
// Definition for a binary// search tree node.class TreeNode { constructor(val) { this.val = val; this.left = null; this.right = null; }}function inorderTraversal(root, values) { if (!root) return; inorderTraversal(root.left, values); values.push(root.val); inorderTraversal(root.right, values);}function getNextGreaterElement(root, target) { // To store the values of the binary // search tree const values = []; // Perform in-order traversal and // store values in the array inorderTraversal(root, values); // Find target value in the array const idx = values.indexOf(target); // If target value is not found, return -1 if (idx === -1) return -1; // Iterate over the array starting from the // target value index for (let i = idx + 1; i < values.length; i++) { // If an element greater than the target // value is found, return it if (values[i] > target) { return values[i]; } } // If next greater element is not found, // return -1 return -1;}// Driver code(function main() { /* * 5 * / \ * 3 7 * / \ / \ * 2 4 6 8 */ const root = new TreeNode(5); root.left = new TreeNode(3); root.right = new TreeNode(7); root.left.left = new TreeNode(2); root.left.right = new TreeNode(4); root.right.left = new TreeNode(6); root.right.right = new TreeNode(8); const target = 4; const nextGreaterElement = getNextGreaterElement(root, target); // Function Call console.log(`The next greater element of ${target} is ${nextGreaterElement}`);})(); |
Output
The next greater element of 4 is 5
Time Complexity: O(n) where n is the number of nodes in the binary search tree.
Auxiliary Space: O(n), to store the node values in a vector.
Approach 2: Recursive Approach
Implementation :
C++
#include <climits>#include <iostream>using namespace std;struct Node { int val; Node* left; Node* right; Node(int value) : val(value) , left(nullptr) , right(nullptr) { }};int findNextGreater(Node* root, int target){ int successor = INT_MAX; while (root) { if (root->val > target) { successor = min(successor, root->val); root = root->left; } else { root = root->right; } } return successor;}int main(){ Node* root = new Node(2); root->left = new Node(4); root->right = new Node(7); root->left->left = new Node(2); root->left->right = new Node(3); root->right->left = new Node(6); root->right->right = new Node(9); int target = 6; int nextGreater = findNextGreater(root, target); cout << "Next greater element after " << target << " is: " << nextGreater << endl; // Clean up the memory delete root->right->right; delete root->right->left; delete root->left->right; delete root->left->left; delete root->right; delete root->left; delete root; return 0;} |
Java
import java.io.*;class Node { int val; Node left; Node right; Node(int value) { val = value; left = null; right = null; }}public class Main { public static int findNextGreater(Node root, int target) { int successor = Integer.MAX_VALUE; while (root != null) { if (root.val > target) { successor = Math.min(successor, root.val); root = root.left; } else { root = root.right; } } return successor; } public static void main(String[] args) { Node root = new Node(2); root.left = new Node(4); root.right = new Node(7); root.left.left = new Node(2); root.left.right = new Node(3); root.right.left = new Node(6); root.right.right = new Node(9); int target = 6; int nextGreater = findNextGreater(root, target); System.out.println("Next greater element after " + target + " is: " + nextGreater); root.right.right = null; root.right.left = null; root.left.right = null; root.left.left = null; root.right = null; root.left = null; root = null; }} |
Python
class Node: def __init__(self, value): self.val = value self.left = None self.right = Nonedef findNextGreater(root, target): successor = float('inf') while root: if root.val > target: successor = min(successor, root.val) root = root.left else: root = root.right return successorif __name__ == "__main__": root = Node(2) root.left = Node(4) root.right = Node(7) root.left.left = Node(2) root.left.right = Node(3) root.right.left = Node(6) root.right.right = Node(9) target = 6 nextGreater = findNextGreater(root, target) print("Next greater element after", target, "is:", nextGreater) root.right.right = None root.right.left = None root.left.right = None root.left.left = None root.right = None root.left = None root = None |
C#
using System;public class Node{ public int val; public Node left; public Node right; public Node(int value) { val = value; left = null; right = null; }}public class GFG{ public static int FindNextGreater(Node root, int target) { int successor = int.MaxValue; while (root != null) { if (root.val > target) { successor = Math.Min(successor, root.val); root = root.left; } else { root = root.right; } } return successor; } public static void Main() { Node root = new Node(2); root.left = new Node(4); root.right = new Node(7); root.left.left = new Node(2); root.left.right = new Node(3); root.right.left = new Node(6); root.right.right = new Node(9); int target = 6; int nextGreater = FindNextGreater(root, target); Console.WriteLine("Next greater element after " + target + " is: " + nextGreater); // Clean up the memory. root.right.right = null; root.right.left = null; root.left.right = null; root.left.left = null; root.right = null; root.left = null; root = null; }} |
Javascript
class Node { constructor(value) { this.val = value; this.left = null; this.right = null; }}function findNextGreater(root, target) { let successor = Number.MAX_SAFE_INTEGER; while (root) { if (root.val > target) { successor = Math.min(successor, root.val); root = root.left; } else { root = root.right; } } return successor;}// Driver codelet root = new Node(2);root.left = new Node(4);root.right = new Node(7);root.left.left = new Node(2);root.left.right = new Node(3);root.right.left = new Node(6);root.right.right = new Node(9);let target = 6;let nextGreater = findNextGreater(root, target);// Clean up the memoryroot.right.right = null;root.right.left = null;root.left.right = null;root.left.left = null;root.right = null;root.left = null;root = null;console.log("Next greater element after " + target + " is: " + nextGreater); |
Output
Next greater element after 6 is: 7
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
