# Largest number in BST which is less than or equal to N

We have a binary search tree and a number N. Our task is to find the greatest number in the binary search tree that is less than or equal to N. Print the value of the element if it exists otherwise print -1.

Examples:
For the above given binary search tree-

```Input : N = 24
Output :result = 21
(searching for 24 will be like-5->12->21)

Input  : N = 4
Output : result = 3
(searching for 4 will be like-5->2->3)
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

We follow recursive approach for solving this problem. We start searching for element from root node. If we reach a leaf and its value is greater than N, element does not exist so return -1. Else if node’s value is less than or equal to N and right value is NULL or greater than N, then return the node value as it will be the answer.
Otherwise if node’s value is greater than N, then search for the element in the left subtree else search for the element in the right subtree by calling the same function by passing the left or right values accordingly.

## C++

 `// C++ code to find the largest value smaller ` `// than or equal to N ` `#include ` `using` `namespace` `std; ` ` `  `struct` `Node { ` `    ``int` `key; ` `    ``Node *left, *right; ` `}; ` ` `  `// To create new BST Node ` `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 ` `Node* insert(Node* node, ``int` `key) ` `{ ` `    ``// if tree is empty return new node ` `    ``if` `(node == NULL) ` `        ``return` `newNode(key); ` ` `  `    ``// if key is less then or grater then ` `    ``// 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; ` `} ` ` `  `// function to find max value less then N ` `int` `findMaxforN(Node* root, ``int` `N) ` `{ ` `    ``// Base cases ` `    ``if` `(root == NULL) ` `        ``return` `-1; ` `    ``if` `(root->key == N) ` `        ``return` `N; ` ` `  `    ``// If root's value is smaller, try in rght ` `    ``// subtree ` `    ``else` `if` `(root->key < N) { ` `        ``int` `k = findMaxforN(root->right, N); ` `        ``if` `(k == -1) ` `            ``return` `root->key; ` `        ``else` `            ``return` `k; ` `    ``} ` ` `  `    ``// If root's key is greater, return value ` `    ``// from left subtree. ` `    ``else` `if` `(root->key > N)  ` `        ``return` `findMaxforN(root->left, N);     ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `N = 4; ` ` `  `    ``// creating following BST ` `    ``/* ` `                  ``5 ` `               ``/     ` `             ``2     12 ` `           ``/      /    ` `          ``1   3   9   21 ` `                     ``/      ` `                    ``19   25  */` `    ``Node* root = insert(root, 25); ` `    ``insert(root, 2); ` `    ``insert(root, 1); ` `    ``insert(root, 3); ` `    ``insert(root, 12); ` `    ``insert(root, 9); ` `    ``insert(root, 21); ` `    ``insert(root, 19); ` `    ``insert(root, 25); ` ` `  `    ``printf``(``"%d"``, findMaxforN(root, N)); ` ` `  `    ``return` `0; ` `} `

## Java

 `// Java code to find the largest value smaller  ` `// 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 = ``null``; ` `    ``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 then or grater then  ` `    ``// 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;  ` `}  ` ` `  `// function to find max value less then N  ` `static` `int` `findMaxforN(Node root, ``int` `N)  ` `{  ` `    ``// Base cases  ` `    ``if` `(root == ``null``)  ` `        ``return` `-``1``;  ` `    ``if` `(root.key == N)  ` `        ``return` `N;  ` ` `  `    ``// If root's value is smaller, try in rght  ` `    ``// subtree  ` `    ``else` `if` `(root.key < N) {  ` `        ``int` `k = findMaxforN(root.right, N);  ` `        ``if` `(k == -``1``)  ` `            ``return` `root.key;  ` `        ``else` `            ``return` `k;  ` `    ``}  ` ` `  `    ``// If root's key is greater, return value  ` `    ``// from left subtree.  ` `    ``else` `if` `(root.key > N)  ` `        ``return` `findMaxforN(root.left, N); ` `    ``return` `-``1``; ` `}  ` ` `  `// Driver code  ` `public` `static` `void` `main(String[] args)  ` `{  ` `    ``int` `N = ``4``;  ` ` `  `    ``// creating following BST  ` `    ``/*  ` `                ``5  ` `            ``/   ` `            ``2     12  ` `        ``/ /   ` `        ``1 3 9 21  ` `                    ``/   ` `                    ``19 25 */` `    ``Node root = ``null``; ` `    ``root = insert(root, ``25``);  ` `    ``insert(root, ``2``);  ` `    ``insert(root, ``1``);  ` `    ``insert(root, ``3``);  ` `    ``insert(root, ``12``);  ` `    ``insert(root, ``9``);  ` `    ``insert(root, ``21``);  ` `    ``insert(root, ``19``);  ` `    ``insert(root, ``25``);  ` ` `  `    ``System.out.println(findMaxforN(root, N));  ` `} ` `}  `

## Python3

 `# Python3 code to find the largest  ` `# value smaller than or equal to N ` `class` `newNode:  ` ` `  `    ``# Constructor to create a new node  ` `    ``def` `__init__(``self``, data):  ` `        ``self``.key ``=` `data  ` `        ``self``.left ``=` `None` `        ``self``.right ``=` `None` ` `  `# To insert a new node in BST  ` `def` `insert(node, key): ` `     `  `    ``# if tree is empty return new node  ` `    ``if` `node ``=``=` `None``:  ` `        ``return` `newNode(key) ` ` `  `    ``# if key is less then or grater then  ` `    ``# 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 ` ` `  `# function to find max value less then N  ` `def` `findMaxforN(root, N): ` `     `  `    ``# Base cases  ` `    ``if` `root ``=``=` `None``:  ` `        ``return` `-``1` `    ``if` `root.key ``=``=` `N:  ` `        ``return` `N ` ` `  `    ``# If root's value is smaller, try in  ` `    ``# right subtree  ` `    ``elif` `root.key < N:  ` `        ``k ``=` `findMaxforN(root.right, N)  ` `        ``if` `k ``=``=` `-``1``: ` `            ``return` `root.key  ` `        ``else``: ` `            ``return` `k ` ` `  `    ``# If root's key is greater, return  ` `    ``# value from left subtree.  ` `    ``elif` `root.key > N:  ` `        ``return` `findMaxforN(root.left, N) ` ` `  `# Driver code  ` `if` `__name__ ``=``=` `'__main__'``: ` `    ``N ``=` `4` ` `  `    ``# creating following BST  ` `    ``#  ` `    ``#             5  ` `    ``#         /   ` `    ``#         2     12  ` `    ``#     / /   ` `    ``#     1 3 9 21  ` `    ``#                 /   ` `    ``#             19 25  ` `    ``root ``=` `None` `    ``root ``=` `insert(root, ``25``) ` `    ``insert(root, ``2``)  ` `    ``insert(root, ``1``)  ` `    ``insert(root, ``3``)  ` `    ``insert(root, ``12``)  ` `    ``insert(root, ``9``)  ` `    ``insert(root, ``21``)  ` `    ``insert(root, ``19``)  ` `    ``insert(root, ``25``)  ` `    ``print``(findMaxforN(root, N))  ` ` `  `# This code is contributed by PranchalK `

## C#

// C# code to find the largest value
// smaller than or equal to N
using System;

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 = null;
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 then or grater then
// 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;
}

// function to find max value less then N
static int findMaxforN(Node root, int N)
{
// Base cases
if (root == null)
return -1;
if (root.key == N)
return N;

// If root’s value is smaller,
// try in right subtree
else if (root.key < N) { int k = findMaxforN(root.right, N); if (k == -1) return root.key; else return k; } // If root's key is greater, return // value from left subtree. else if (root.key > N)
return findMaxforN(root.left, N);
return -1;
}

// Driver code
public static void Main(String[] args)
{
int N = 4;

// creating following BST
/*
5
/
2 12
/ /
1 3 9 21
/
19 25 */
Node root = null;
root = insert(root, 25);
insert(root, 2);
insert(root, 1);
insert(root, 3);
insert(root, 12);
insert(root, 9);
insert(root, 21);
insert(root, 19);
insert(root, 25);

Console.WriteLine(findMaxforN(root, N));
}
}

// This code is contributed 29AjayKumar

Output:

```3
```

Time complexity: O(h) where h is height of BST.