Find next smaller element in Binary Search Tree
Given a binary search tree and a target value, the task is to find the next smaller element of the target value in the binary search tree.
Examples :
Input:
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13Target: 7
Output: 6
Explanation: The next smaller element of 7 is 6Input:
6
/ \
4 8
/ \ / \
2 5 7 10Target: 5
Output: 4
Explanation: The next smaller element of 5 is 4
Approach1:
This approach to solve the problem is to do inorder traversal of the BST given and store each node while traversing in an array. Now, since inorder traversal of BST gives sorted elements, so we can do binary search to find next smaller element of target value in the array itself.
Below are the steps for the above approach:
- Define a structure for the node of the BST containing data, and pointers to the left and right child nodes.
- Create a function called βinorderβ that takes the root node and a reference to an integer vector as parameters.
- Inside the βinorderβ function, if the root node is NULL, return. Else, perform an inorder traversal of the BST by calling βinorderβ recursively for the left child, pushing the data of the root node to the vector, and calling βinorderβ recursively for the right child.
- Create a function called βnextSmallerElementβ that takes the root node and the target value as parameters.
- Inside the βnextSmallerElementβ function, call the βinorderβ function passing the root node and a reference to a vector as parameters to store the inorder traversal of the BST.
- Get the size of the vector and initialize two variables left and right to 0 and n-1, respectively.
- Initialize an integer variable βindexβ to -1.
- While the left index is less than or equal to the right index, calculate the middle index using the formula (left + right) / 2.
- If the value at the middle index of the vector is less than the target value, set the βindexβ variable to the middle index, and move the βleftβ variable to mid+1.
- Else, set the βrightβ variable to mid-1.
- If no smaller element exists, return -1. Else, return the value at the βindexβ position in the vector.
- Create the root node of the BST, insert some nodes into the BST, and initialize the target value.
- Call the βnextSmallerElementβ function passing the root node and the target value as parameters.
- Print the returned value from the βnextSmallerElementβ function.
Below is the code for the above approach:
C++
// C++ program to find next smaller element // in BST #include <bits/stdc++.h> using namespace std; // Structure of a node of BST struct Node { int data; Node *left, *right; Node( int val) { data = val; left = right = NULL; } }; // Function to do inorder traversal of BST void inorder(Node* root, vector< int >& nodes) { if (root == NULL) return ; inorder(root->left, nodes); nodes.push_back(root->data); inorder(root->right, nodes); } // nodes Function to find next smaller element // in BST int nextSmallerElement(Node* root, int target) { // Stores inorder traversal of BST vector< int > nodes; inorder(root, nodes); int n = nodes.size(); // Performing binary search to find // next smaller element of target int left = 0, right = n - 1; int index = -1; while (left <= right) { int mid = left + (right - left) / 2; if (nodes[mid] < target) { index = mid; left = mid + 1; } else right = mid - 1; } // If no smaller element exists if (index == -1) return -1; return nodes[index]; } // Driver code int main() { // Create the binary search tree Node* root = new Node(8); root->left = new Node(3); root->left->left = new Node(1); root->left->right = new Node(6); root->left->right->left = new Node(4); root->left->right->right = new Node(7); root->right = new Node(10); root->right->right = new Node(14); root->right->right->left = new Node(13); int target = 7; // Function call cout << nextSmallerElement(root, target); return 0; } |
Java
// Java program to find next smaller element // in BST import java.util.*; class GFG { // Structure of a node of BST static class Node { int data; Node left, right; Node( int val) { data = val; left = right = null ; } } // Function to do inorder traversal of BST static void inorder(Node root, List<Integer> nodes) { if (root == null ) return ; inorder(root.left, nodes); nodes.add(root.data); inorder(root.right, nodes); } // Function to find next smaller element in BST static int nextSmallerElement(Node root, int target) { // Stores inorder traversal of BST List<Integer> nodes = new ArrayList<>(); inorder(root, nodes); int n = nodes.size(); // Performing binary search to find next smaller element of target int left = 0 , right = n - 1 ; int index = - 1 ; while (left <= right) { int mid = left + (right - left) / 2 ; if (nodes.get(mid) < target) { index = mid; left = mid + 1 ; } else { right = mid - 1 ; } } // If no smaller element exists if (index == - 1 ) return - 1 ; return nodes.get(index); } // Driver code public static void main(String[] args) { // Create the binary search tree Node root = new Node( 8 ); root.left = new Node( 3 ); root.left.left = new Node( 1 ); root.left.right = new Node( 6 ); root.left.right.left = new Node( 4 ); root.left.right.right = new Node( 7 ); root.right = new Node( 10 ); root.right.right = new Node( 14 ); root.right.right.left = new Node( 13 ); int target = 7 ; // Function call System.out.println(nextSmallerElement(root, target)); } } // This code is contributed by Pushpesh Raj |
Python3
# Python3 program to find next smaller element # in BST # Structure of a node of BST class Node: def __init__( self , val): self .data = val self .left = None self .right = None # Function to do inorder traversal of BST def inorder(root, nodes): if root is None : return inorder(root.left, nodes) nodes.append(root.data) inorder(root.right, nodes) #Function to find next smaller element in BST def next_smaller_element(root, target): nodes = [] inorder(root, nodes) n = len (nodes) # Performing binary search to find next smaller element of target left = 0 right = n - 1 index = - 1 while left < = right: mid = left + (right - left) / / 2 if nodes[mid] < target: index = mid left = mid + 1 else : right = mid - 1 if index = = - 1 : return - 1 return nodes[index] # Driver code root = Node( 8 ) root.left = Node( 3 ) root.left.left = Node( 1 ) root.left.right = Node( 6 ) root.left.right.left = Node( 4 ) root.left.right.right = Node( 7 ) root.right = Node( 10 ) root.right.right = Node( 14 ) root.right.right.left = Node( 13 ) target = 7 # Function call print (next_smaller_element(root, target)) |
C#
// C# program to find next smaller element // in BST using System; using System.Collections.Generic; // Structure of a node of BST public class Node { public int data; public Node left, right; public Node( int val) { data = val; left = right = null ; } } public class GFG { // Function to do inorder traversal of BST and store // nodes in a list public static void Inorder(Node root, List< int > nodes) { if (root == null ) return ; Inorder(root.left, nodes); nodes.Add(root.data); Inorder(root.right, nodes); } // Function to find next smaller element in BST public static int NextSmallerElement(Node root, int target) { // Stores inorder traversal of BST List< int > nodes = new List< int >(); Inorder(root, nodes); int n = nodes.Count; // Performing binary search to find next smaller // element of target int left = 0, right = n - 1; int index = -1; while (left <= right) { int mid = left + (right - left) / 2; if (nodes[mid] < target) { index = mid; left = mid + 1; } else right = mid - 1; } // If no smaller element exists if (index == -1) return -1; return nodes[index]; } // Driver code public static void Main() { // Create the binary search tree Node root = new Node(8); root.left = new Node(3); root.left.left = new Node(1); root.left.right = new Node(6); root.left.right.left = new Node(4); root.left.right.right = new Node(7); root.right = new Node(10); root.right.right = new Node(14); root.right.right.left = new Node(13); int target = 7; // Function call Console.WriteLine(NextSmallerElement(root, target)); } } // This code is contributed by Susobhan Akhuli |
Javascript
// JavaScript program to find next smaller element // in BST // Definition of a node in BST class Node { constructor(val) { this .data = val; this .left = null ; this .right = null ; } } // Function to perform an inorder traversal of BST function inorder(root, nodes) { if (root === null ) return ; inorder(root.left, nodes); nodes.push(root.data); inorder(root.right, nodes); } // Function to find the next smaller element in BST function nextSmallerElement(root, target) { // Store inorder traversal of BST const nodes = []; inorder(root, nodes); const n = nodes.length; // Perform binary search to find the next smaller element let left = 0; let right = n - 1; let index = -1; while (left <= right) { const mid = Math.floor((left + right) / 2); if (nodes[mid] < target) { index = mid; left = mid + 1; } else { right = mid - 1; } } // If no smaller element exists if (index === -1) return -1; return nodes[index]; } // Create the binary search tree const root = new Node(8); root.left = new Node(3); root.left.left = new Node(1); root.left.right = new Node(6); root.left.right.left = new Node(4); root.left.right.right = new Node(7); root.right = new Node(10); root.right.right = new Node(14); root.right.right.left = new Node(13); const target = 7; // Function call document.write(nextSmallerElement(root, target)); // This code is contributed by Susobhan Akhuli |
6
Time Complexity: O(N) where N is number of nodes in the BST given. This is because we are traversing each node of the tree.
Space Complexity: O(N) as we are storing nodes values in vector nodes. Here, N is number of nodes in the BST given.
Approach: To solve the problem follow the below idea:
Traverse the binary search tree to find the target node. If the target node has a left child, then the next smaller element will be the rightmost node in the left subtree. If the target node does not have a left child, then the next smaller element will be the first ancestor node that is greater than the target node.
Below are the steps for the above approach:
- Initialize a variable to store the next smaller element.
- Traverse the binary search tree to find the target node.
- If the target node has a left child, then traverse the right subtree of the left child until the rightmost node is found.
- If the target node does not have a left child, then traverse the ancestors of the target node until an ancestor node is found that is greater than the target node. Update the next smaller element if the ancestor node is smaller than the current next smaller element.
- Return the next smaller element.
Below is the code for the above approach:
C++
// C++ code for the above approach: #include <iostream> using namespace std; // Definition of a binary search tree node struct Node { int value; Node* left; Node* right; Node( int val) { value = val; left = NULL; right = NULL; } }; // Function to find the next smaller // element in a binary search tree int findNextSmaller(Node* root, int target) { int nextSmaller = -1; Node* curr = root; // Traverse the binary search tree to // find the target node while (curr != NULL) { if (curr->value == target) { // If the target node has a // left child, then the next // smaller element will be // the rightmost node in the // left subtree if (curr->left != NULL) { curr = curr->left; while (curr->right != NULL) { curr = curr->right; } nextSmaller = curr->value; } break ; } else if (curr->value > target) { curr = curr->left; } else { // If the current node is // smaller than the target node, // then update the next smaller // element if the current node // is greater than the current // next smaller element if (curr->value > nextSmaller) { nextSmaller = curr->value; } curr = curr->right; } } return nextSmaller; } // Driver code int main() { // Create the binary search tree Node* root = new Node(8); root->left = new Node(3); root->left->left = new Node(1); root->left->right = new Node(6); root->left->right->left = new Node(4); root->left->right->right = new Node(7); root->right = new Node(10); root->right->right = new Node(14); root->right->right->left = new Node(13); int target1 = 7; // Function call int result1 = findNextSmaller(root, target1); cout << result1 << endl; return 0; } |
Java
// Java code for the above approach: import java.io.*; // Definition of a binary search tree node class Node { int value; Node left; Node right; Node( int val) { value = val; left = null ; right = null ; } } // Function to find the next smaller // element in a binary search tree class GFG { static int findNextSmaller(Node root, int target) { int nextSmaller = - 1 ; Node curr = root; // Traverse the binary search tree to // find the target node while (curr != null ) { if (curr.value == target) { // If the target node has a // left child, then the next // smaller element will be // the rightmost node in the // left subtree if (curr.left != null ) { curr = curr.left; while (curr.right != null ) { curr = curr.right; } nextSmaller = curr.value; } break ; } else if (curr.value > target) { curr = curr.left; } else { // If the current node is // smaller than the target node, // then update the next smaller // element if the current node // is greater than the current // next smaller element if (curr.value > nextSmaller) { nextSmaller = curr.value; } curr = curr.right; } } return nextSmaller; } // Driver code public static void main(String args[]) { // Create the binary search tree Node root = new Node( 8 ); root.left = new Node( 3 ); root.left.left = new Node( 1 ); root.left.right = new Node( 6 ); root.left.right.left = new Node( 4 ); root.left.right.right = new Node( 7 ); root.right = new Node( 10 ); root.right.right = new Node( 14 ); root.right.right.left = new Node( 13 ); int target1 = 7 ; // Function call int result1 = findNextSmaller(root, target1); System.out.println(result1); } } |
Python3
# Python code for the above approach # Definition of a binary search tree node class Node: def __init__( self , val): self .value = val self .left = None self .right = None # Function to find the next smaller element in a binary search tree def findNextSmaller(root, target): nextSmaller = - 1 curr = root # Traverse the binary search tree to find the target node while curr is not None : if curr.value = = target: # If the target node has a left child, then the next # smaller element will be the rightmost node in the left subtree if curr.left is not None : curr = curr.left while curr.right is not None : curr = curr.right nextSmaller = curr.value break elif curr.value > target: curr = curr.left else : # If the current node is smaller than the target node, # then update the next smaller element if the current node # is greater than the current next smaller element if curr.value > nextSmaller: nextSmaller = curr.value curr = curr.right return nextSmaller # Driver code if __name__ = = '__main__' : # Create the binary search tree root = Node( 8 ) root.left = Node( 3 ) root.left.left = Node( 1 ) root.left.right = Node( 6 ) root.left.right.left = Node( 4 ) root.left.right.right = Node( 7 ) root.right = Node( 10 ) root.right.right = Node( 14 ) root.right.right.left = Node( 13 ) target1 = 7 # Function call result1 = findNextSmaller(root, target1) print (result1) # This code is contributed by Susobhan Akhuli |
C#
// C# code for the above approach: using System; // Definition of a binary search tree node public class Node { public int value; public Node left; public Node right; public Node( int val) { value = val; left = null ; right = null ; } } public class GFG { static int findNextSmaller(Node root, int target) { int nextSmaller = -1; Node curr = root; // Traverse the binary search tree to find the // target node while (curr != null ) { if (curr.value == target) { // If the target node has a left child, then // the next smaller element will be the // rightmost node in the left subtree if (curr.left != null ) { curr = curr.left; while (curr.right != null ) { curr = curr.right; } nextSmaller = curr.value; } break ; } else if (curr.value > target) { curr = curr.left; } else { // If the current node is smaller than the // target node, then update the next smaller // element if the current node is greater // than the current next smaller element if (curr.value > nextSmaller) { nextSmaller = curr.value; } curr = curr.right; } } return nextSmaller; } static public void Main() { // Code // Create the binary search tree Node root = new Node(8); root.left = new Node(3); root.left.left = new Node(1); root.left.right = new Node(6); root.left.right.left = new Node(4); root.left.right.right = new Node(7); root.right = new Node(10); root.right.right = new Node(14); root.right.right.left = new Node(13); int target1 = 7; // Function call int result1 = findNextSmaller(root, target1); Console.WriteLine(result1); } } // This code is contributed by karthik. |
Javascript
// Definition of a binary search tree node class Node { constructor(val) { this .value = val; this .left = null ; this .right = null ; } } // Function to find the next smaller // element in a binary search tree function findNextSmaller(root, target) { let nextSmaller = -1; let curr = root; // Traverse the binary search tree to // find the target node while (curr !== null ) { if (curr.value === target) { // If the target node has a // left child, then the next // smaller element will be // the rightmost node in the // left subtree if (curr.left !== null ) { curr = curr.left; while (curr.right !== null ) { curr = curr.right; } nextSmaller = curr.value; } break ; } else if (curr.value > target) { curr = curr.left; } else { // If the current node is // smaller than the target node, // then update the next smaller // element if the current node // is greater than the current // next smaller element if (curr.value > nextSmaller) { nextSmaller = curr.value; } curr = curr.right; } } return nextSmaller; } // Driver code function main() { // Create the binary search tree const root = new Node(8); root.left = new Node(3); root.left.left = new Node(1); root.left.right = new Node(6); root.left.right.left = new Node(4); root.left.right.right = new Node(7); root.right = new Node(10); root.right.right = new Node(14); root.right.right.left = new Node(13); const target1 = 7; // Function call const result1 = findNextSmaller(root, target1); console.log(result1); } // Call the main function main(); |
6
Time Complexity: O(h)
Auxiliary Space: O(1)
Contact Us