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 code int 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 node class 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 vector def 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 tree def 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 code if __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}`); })(); |
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 = None def 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 successor if __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 code let 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 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 ; console.log( "Next greater element after " + target + " is: " + nextGreater); |
Next greater element after 6 is: 7
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!