Blog

Introduction:

In this guide, we’ll actively discover ‘The Greatest Value Node’ within a Binary Search Tree (BST), ensuring it’s either smaller or equal to a specified number ‘x’ using Python. We’ll guide you step by step to make it easy to grasp, even if you’re new to programming. So, let’s begin and learn how to reveal this valuable node in a BST using the Python language.

Question:

You are given a BST(Binary Search Tree) with n number of nodes and value x. your task is to find the greatest value node of the BST which is smaller than or equal to x.
Note: when x is smaller than the smallest node of BST then returns -1.

Example 1:

Input:

n = 7

BST:
     2
      \
       81
      /  \
     42   87
      \     \
       66    90
      /
     45

x = 87

Output:

87

Explanation:

87 is present in tree so floor will be 87.

Example 2:

Input:

n = 4

                          6
                           \
                            8
                          /   \
                        7       9

x = 11

Output: 9

Your Task:

You don’t need to read input or print anything. Complete the function floor() which takes the integer n and BST and integer x returns the floor value.

Constraint:
1 <= Noda data <= 10⁹
1 <= n <= 10⁵

Expected Time Complexity: O(n)
Expected Space Complexity: O(1)

Answer:

class Solution:
    def floor(self, root, x):
        result = -1  # Initialize result as -1

        while root:
            if root.data == x:
                return root.data
            elif root.data < x:
                result = root.data  # Update result when the current node value is less than or equal to x
                root = root.right
            else:
                root = root.left

        return result

How do we find the largest value in a Binary Search Tree (BST) that’s less than or equal to a given number ‘x’ using Python?

1. Start at the top: We begin at the very top of the tree, which is called the root.
2. Set our initial answer: We have a variable called ‘answer,’ and we set it to -1. This variable keeps track of our best guess for the largest value that’s less than or equal to ‘x.’
3. Explore the tree: We keep looking through the tree until we’ve checked every node. At each node:
   • We check the value: We look at the number on that node.
   • Compare with ‘x’: We compare this number to ‘x.’
   • Three possibilities: There are three things that can happen:
     • If the number is exactly ‘x,’ we found what we were looking for, so we can stop and return this number.
     • If the number is less than ‘x,’ we update our ‘answer’ to this number because it’s a good candidate for the largest value that’s less than or equal to ‘x.’ We then move to the right because the larger values are on the right side.
     • If the number is greater than ‘x,’ we move to the left because the smaller values are on the left side.
4. Giving our answer: Once we’ve looked at all the nodes, we return the ‘answer.’ This ‘answer’ is the largest value in the BST that’s less than or equal to ‘x.’

This method helps us efficiently find the value we’re looking for in the Binary Search Tree, which is like a well-organized library for numbers. It’s especially helpful when we want to find specific numbers within a big list of them.

Explore More Questions on Our Site

If you’re eager to delve into more fascinating questions and discover solutions to various topics, visit our website. We have a wide range of articles and guides on programming, technology, and numerous other subjects. Explore, learn, and expand your knowledge today!

Visit Our Website

Above question Contest is Available on Geeks Of Geeks to solve this problem

Conclusion:

In this guide, we’ve embarked on a journey to find the ‘Greatest Value Node’ within a Binary Search Tree (BST) using Python. By actively exploring this efficient approach, we’ve learned how to uncover the largest value that’s smaller or equal to a specified number ‘x.’ With these newfound skills, you’re better equipped to navigate and extract valuable data from structured datasets like a BST. Keep exploring, keep learning, and continue your programming adventures with confidence.