Question
Quest for the Inorder Predecessor
In a faraway kingdom, there exists a Tree of Wisdom, a special Binary Search Tree (BST) where every node contains a magical integer value. The root of this tree is given to you.
The king seeks the greatest value in the tree that is less than or equal to a given number k — this value is called the inorder predecessor of k.
Your task is to help the king find this value.
If no such value exists in the tree (i.e., all values are greater than k), return None.
Input
Your Task
Since this is a functional problem, you do not need to handle input or output. Your task is to complete the function findFloor(), which takes the root of the BST and an integer k as input parameters, and returns the largest Node in the BST that is less than or equal to k. If no such value exists, return None.
Custom Input
The first line of input contains an integer, N, representing the number of nodes in the tree.
The next line consists of space-separated integers denoting the level order traversal of the tree, where non-negative values represent node values, and -1 indicates a null node.
The third line of the input contains a single integer k.
Note: Once a node is marked as -1, no further information about its children is provided.
Since this is a functional problem, you do not need to handle input or output. Your task is to complete the function findFloor(), which takes the root of the BST and an integer k as input parameters, and returns the largest Node in the BST that is less than or equal to k. If no such value exists, return None.
Custom Input
The first line of input contains an integer, N, representing the number of nodes in the tree.
The next line consists of space-separated integers denoting the level order traversal of the tree, where non-negative values represent node values, and -1 indicates a null node.
The third line of the input contains a single integer k.
Note: Once a node is marked as -1, no further information about its children is provided.
Output
Return the largest Node in the BST that is less than or equal to the given integer k if it exists; otherwise, return None.
Example
Input:
6
5 3 6 2 4 -1 -1 1
5
Output:
5
Input:
6
5 3 6 2 4 -1 -1 1
1
Output:
1
6
5 3 6 2 4 -1 -1 1
5
Output:
5
Input:
6
5 3 6 2 4 -1 -1 1
1
Output:
1