Given a Binary Search Tree and a number N, the task is to find the smallest number in the binary search tree that is greater than or equal to N.
Examples:
Input: N = 5
8
/ \
7 10
/ / \
2 9 13
Output: 7
As 7 is the smallest number in BST which is greater than N = 5.
Input: N = 10
8
/ \
5 11
/ \
2 7
\
3
Output: 11
As 11 is the smallest number in BST which is greater than N = 10.
A recursive solution for this problem has been already been discussed in this post. Below is an iterative approach for the problem:
Using Morris Traversal the above problem can be solved in constant space. Find the inorder successor of the target. Keep two pointers, one pointing to the current node and one for storing the answer.
Below is the implementation of the above approach:
C++
// C++ code to find the smallest value greater// than or equal to N#include <bits/stdc++.h>using namespace std;struct Node { int key; Node *left, *right;};// To create new BST NodeNode* newNode(int item){ Node* temp = new Node; temp->key = item; temp->left = temp->right = NULL; return temp;}// To insert a new node in BSTNode* insert(Node* node, int key){ // if tree is empty return new node if (node == NULL) return newNode(key); // if key is less than or greater than // node value then recur down the tree if (key < node->key) node->left = insert(node->left, key); else if (key > node->key) node->right = insert(node->right, key); // return the (unchanged) node pointer return node;}// Returns smallest value greater than or // equal to key.int findFloor(Node* root, int key){ Node *curr = root, *ans = NULL; // traverse in the tree while (curr) { // if the node is smaller than N, // move right. if (curr->key > key) { ans = curr; curr = curr->left; } // if it is equal to N, then it will be // the answer else if (curr->key == key) { ans = curr; break; } else // move to the right of the tree curr = curr->right; } if (ans != NULL) return ans->key; return -1;}// Driver codeint main(){ int N = 13; Node* root = insert(root, 19); insert(root, 2); insert(root, 1); insert(root, 3); insert(root, 12); insert(root, 9); insert(root, 21); insert(root, 25); printf("%d", findFloor(root, 15)); return 0;} |
Java
// Java code to find the smallest value greater // than or equal to N class GFG { static class Node { int key; Node left, right; }; // To create new BST Node static Node newNode(int item) { Node temp = new Node(); temp.key = item; temp.left = temp.right = null; return temp; } // To insert a new node in BST static Node insert(Node node, int key) { // if tree is empty return new node if (node == null) { return newNode(key); } // if key is less than or greater than // node value then recur down the tree if (key < node.key) { node.left = insert(node.left, key); } else if (key > node.key) { node.right = insert(node.right, key); } // return the (unchanged) node pointer return node; } // Returns smallest value greater than or // equal to key. static int findFloor(Node root, int key) { Node curr = root, ans = null; // traverse in the tree while (curr != null) { // if the node is smaller than N, // move right. if (curr.key > key) { ans = curr; curr = curr.left; } // if it is equal to N, then it will be // the answer else if (curr.key == key) { ans = curr; break; } else // move to the right of the tree { curr = curr.right; } } if (ans != null) { return ans.key; } return -1; } // Driver code public static void main(String[] args) { int N = 13; Node root = new Node(); insert(root, 19); insert(root, 2); insert(root, 1); insert(root, 3); insert(root, 12); insert(root, 9); insert(root, 21); insert(root, 25); System.out.printf("%d", findFloor(root, 15)); }}// This code is contributed by Rajput-Ji |
Python3
# Python3 code to find the smallest # value greater than or equal to Nclass Node: def __init__(self, key): self.key = key self.left = None self.right = None# To insert a new node in BSTdef insert(node: Node, key: int) -> Node: # If tree is empty return new node if (node is None): return Node(key) # If key is less than or greater than # node value then recur down the tree if (key < node.key): node.left = insert(node.left, key) elif (key > node.key): node.right = insert(node.right, key) # Return the (unchanged) node pointer return node# Returns smallest value greater than or# equal to key.def findFloor(root: Node, key: int) -> int: curr = root ans = None # Traverse in the tree while (curr): # If the node is smaller than N, # move right. if (curr.key > key): ans = curr curr = curr.left # If it is equal to N, then # it will be the answer elif (curr.key == key): ans = curr break else: # Move to the right of the tree curr = curr.right if (ans != None): return ans.key return -1# Driver codeif __name__ == "__main__": N = 13 root = None root = insert(root, 19) insert(root, 2) insert(root, 1) insert(root, 3) insert(root, 12) insert(root, 9) insert(root, 21) insert(root, 25) print(findFloor(root, 15))# This code is contributed by sanjeev2552 |
C#
// C# code to find the smallest value greater // than or equal to N using System;using System.Collections.Generic;class GFG { class Node { public int key; public Node left, right; }; // To create new BST Node static Node newNode(int item) { Node temp = new Node(); temp.key = item; temp.left = temp.right = null; return temp; } // To insert a new node in BST static Node insert(Node node, int key) { // if tree is empty return new node if (node == null) { return newNode(key); } // if key is less than or greater than // node value then recur down the tree if (key < node.key) { node.left = insert(node.left, key); } else if (key > node.key) { node.right = insert(node.right, key); } // return the (unchanged) node pointer return node; } // Returns smallest value greater than or // equal to key. static int findFloor(Node root, int key) { Node curr = root, ans = null; // traverse in the tree while (curr != null) { // if the node is smaller than N, // move right. if (curr.key > key) { ans = curr; curr = curr.left; } // if it is equal to N, then it will be // the answer else if (curr.key == key) { ans = curr; break; } else // move to the right of the tree { curr = curr.right; } } if (ans != null) { return ans.key; } return -1; } // Driver code public static void Main(String[] args) { Node root = new Node(); insert(root, 19); insert(root, 2); insert(root, 1); insert(root, 3); insert(root, 12); insert(root, 9); insert(root, 21); insert(root, 25); Console.Write("{0}", findFloor(root, 15)); }}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript code to find the smallest// value greater than or equal to N class Node { constructor() { this.key = 0; this.left = null; this.right = null; }};// To create new BST Node function newNode(item) { var temp = new Node(); temp.key = item; temp.left = temp.right = null; return temp;}// To insert a new node in BST function insert(node, key) { // If tree is empty return new node if (node == null) { return newNode(key); } // If key is less than or greater than // node value then recur down the tree if (key < node.key) { node.left = insert(node.left, key); } else if (key > node.key) { node.right = insert(node.right, key); } // Return the (unchanged) node pointer return node;}// Returns smallest value greater than or // equal to key. function findFloor(root, key) { var curr = root, ans = null; // Traverse in the tree while (curr != null) { // If the node is smaller than N, // move right. if (curr.key > key) { ans = curr; curr = curr.left; } // If it is equal to N, then it will be // the answer else if (curr.key == key) { ans = curr; break; } // Move to the right of the tree else { curr = curr.right; } } if (ans != null) { return ans.key; } return -1;}// Driver code var root = new Node();insert(root, 19);insert(root, 2);insert(root, 1);insert(root, 3);insert(root, 12);insert(root, 9);insert(root, 21);insert(root, 25);document.write(findFloor(root, 15));// This code is contributed by rutvik_56</script> |
Output
19
Complexity Analysis:
- Time complexity: O(N)
- Auxiliary Space: O(1)
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!
