Check if Tree is BST 🎯

Welcome to our comprehensive guide on checking if a tree is a Binary Search Tree (BST)! In this lesson, we'll dive deep into understanding what a BST is, why it matters, and how to determine if a given tree adheres to the BST properties. Let's get started!

What is a Binary Search Tree (BST)? 📝

A Binary Search Tree is a type of binary tree data structure where the nodes are arranged in such a way that the keys of the left subtree are less than the root's key, and the keys of the right subtree are greater than the root's key. This property allows for efficient searching, insertion, and deletion of elements.

💡 Pro Tip: BSTs are useful for maintaining sorted data efficiently and are widely used in various real-world applications like databases, filesystems, and computer graphics.

Properties of a Binary Search Tree 📝

A BST must follow these properties:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
Each node's left and right subtrees are also binary search trees.

Checking if a Tree is BST 💡

Now, let's discuss the algorithm to check if a given tree is a Binary Search Tree. We'll implement two methods: isBST(root) and isValidBST(root, min, max).

isBST(root) 📝

The isBST(root) method checks if a given tree is a BST by recursively traversing the tree and checking the properties of the BST.

python

def isBST(root):
    if root is None:
        return True

    if not isBST(root.left) or (root.left and root.left.data >= root.data):
        return False

    if root.right and root.right.data <= root.data:
        return False

    return isBST(root.left) and isBST(root.right)

💡 Pro Tip: The isBST(root) method checks the properties of a BST but does not provide the minimum and maximum values of the tree. To get these values, we'll use the isValidBST(root, min, max) method.

isValidBST(root, min, max) 📝

The isValidBST(root, min, max) method checks if a given tree is a BST within the given minimum and maximum bounds.

python

def isValidBST(root, min, max):
    if root is None:
        return True

    if root.data <= min or (root.data >= max and root.left is not None):
        return False

    return isValidBST(root.left, min, root.data) and isValidBST(root.right, root.data, max)

💡 Pro Tip: The isValidBST(root, min, max) method can be used to find the minimum and maximum values of a BST by setting min to negative infinity, max to positive infinity before the recursive call, and updating the values after the recursive call.

Quiz 💡

With this lesson, you now have a solid understanding of what a Binary Search Tree is and how to check if a given tree adheres to the properties of a BST. Keep practicing, and soon you'll be able to implement efficient data structures and algorithms in your own projects! 🚀

Happy coding! 💻