BST Verification Algorithm

Introduction

Welcome to Art Of Coding! In this post, we tackle a crucial question in the realm of data structures: Is Your Tree a BST?

Previously, we delved into BST basics, including node insertion and in-order tree traversal. Now, we’re taking a step further to discuss an algorithm that checks if a tree is indeed a BST. Verifying Binary Search Trees (BSTs) is an essential skill, not just for academic purposes but also for coding interviews.

In this article, we’ll provide clear, concise explanations, accompanied by practical Java code examples. This approach will help you grasp the concept thoroughly and apply it confidently in your coding endeavors. At the end of this post, we’ll also include a link to a related problem on LeetCode, allowing you to test your understanding in a real-world scenario.

Let’s unravel the intricacies of BST verification together with Java!

Understanding BST Verification

BST Properties

Before we start, let’s quickly recap what makes a tree a Binary Search Tree (BST).

A BST is a binary tree in which every node follows the BST property: the key in each node is greater than all keys in the node’s left subtree and smaller than those in its right subtree. This property must hold for every node in the tree, not just the root.

To visualize what a proper BST looks like, consider the following image:

This image shows a binary tree with the root node as 10, which perfectly meets the BST conditions. In the left subtree, node 5 serves as the root with children nodes 3 and 6, both positioned correctly according to BST rules. Similarly, in the right subtree, node 15 serves as the root with children nodes 12 and 18, also adhering to the BST requirements. This tree is a classic BST example, where each node’s left child holds a smaller value and the right child a larger value, thus meeting the BST criteria at every level.

Exploring the BST Validation Process

Now that we have a visual understanding, let’s discuss the algorithm for verifying whether a binary tree qualifies as a BST. This process involves traversing the tree in a way that adheres to the BST properties, ensuring each node’s value falls within an allowable range dictated by its position in the tree. We achieve this through a depth-first search (DFS) traversal, where we check each node’s value against the range its ancestors define.

To further clarify this concept, examine the annotated diagram below:

In this detailed diagram, each node in the BST is annotated with the permissible range of values it can hold, utilizing the concepts of minus infinity (-∞) and plus infinity (∞). These annotations are crucial for understanding how the algorithm verifies the BST properties at each node. Let’s look at some examples:

The root node, 10, has an initial range from -∞ to ∞, signifying that, as the first node, it can take any value. In a BST, the root node is where the validation starts, and thus it is not constrained by the values of any parent nodes.
The left child of the root, node 5, has a range from -∞ to 10. This is because it is a left descendant of the root, and therefore, it must contain a value less than 10 to satisfy the BST property. The maximum value it can take is one less than the root node’s value, ensuring it remains less than any value the root node or its right subtree might hold.
The right child of node 5, node 6, must have a value greater than 5 and less than 10, giving it a range from 5 to 10. This confirms that it is greater than all nodes in the left subtree of its parent (node 5) and less than its parent’s parent (node 10).

Java Implementation of BST Verification

public class TreeUtil {

    public static boolean isBst(Node node) {
        return isBst(node, null, null);
    }

    private static boolean isBst(Node root, Integer minValue, Integer maxValue) {
        if (root == null) {
            return true;
        }

        if ((minValue == null || minValue < root.getElement()) && (maxValue == null || maxValue > root.getElement())) {
            boolean leftIsBst = isBst(root.getLeft(), minValue, root.getElement());
            boolean rightIsBst = isBst(root.getRight(), root.getElement(), maxValue);
            return leftIsBst && rightIsBst;
        } else {
            return false;
        }
    }
}

Detailed Explanation of the isBst Method

public class Node {

    private int element;
    private Node left;
    private Node right;

    public Node(int data) {
        this.element = data;
    }

    public int getElement() {
        return element;
    }

    public Node getLeft() {
        return left;
    }

    public Node getRight() {
        return right;
    }
}

The TreeUtil class designs the isBst method to validate the integrity of a binary search tree.. Here’s a breakdown of how the method works:

Base Case: The method begins with a base case check: if (root == null). If the current node being checked (root) is null, it means we’ve reached the end of a branch, and by definition, a null branch can be considered a valid BST. Therefore, the method returns true.
Value Check: Next, the method checks whether the current node’s value (root.getElement()) falls within the permissible range. It does this by comparing the node’s value with minValue and maxValue.
- minValue represents the minimum value a node can have. It starts as null (minus infinity) and gets updated to the parent node’s value when moving to the right subtree, reflecting that all values in the right subtree should be greater than the parent node’s value.
- maxValue represents the maximum value a node can have. It is initially null (plus infinity) and is updated to the parent node’s value when moving to the left subtree. This ensures that all values in the left subtree are less than the parent node’s value.
- By initializing these parameters as null, we allow the root of the tree to have any integer value, effectively setting the initial range from minus infinity to plus infinity.
Recursive Calls: If the current node’s value is within the permissible range, the method makes two recursive calls:
- It calls itself with the current node’s left child (root.getLeft()), updating the maxValue to the current node’s value (root.getElement()), since the left child must contain a smaller value than its parent.
- It calls itself with the current node’s right child (root.getRight()), updating the minValue to the current node’s value, because the right child must contain a larger value than its parent.
Combining Results: After the recursive calls, the method then combines the results: return leftIsBst && rightIsBst;. This step ensures that both the left and right subtrees must be valid BSTs for the current subtree to be considered a BST. If either subtree is not a BST, the method will return false.

Complexity Analysis

Time Complexity

Traversal: At its core, this algorithm performs a depth-first search (DFS) traversal of the tree. In DFS, each node is visited exactly once.
Complexity: Since each node in the tree is visited once, the time complexity of the isBst method is O(N), where N is the number of nodes in the tree. This makes it a linear time algorithm with respect to the number of nodes.

Space Complexity

Recursive Calls: The most significant factor contributing to space complexity is the recursive calls made during the tree traversal. The depth of these recursive calls is proportional to the height of the tree.
Complexity: In the best-case scenario (a balanced tree), the height of the tree would be log(N), resulting in a space complexity of O(log(N)). However, in the worst case (a skewed tree, where the tree takes the form of a linear chain), the space complexity would be O(N), as the depth of the recursive stack would be equal to the number of nodes.

To visualize the space complexity in a skewed tree, which represents the worst-case scenario for our isBst algorithm, let’s look at the following image:

The isBst algorithm is efficient in terms of time, as it runs in linear time relative to the size of the tree. However, its space efficiency depends on the tree’s structure. It is more space-efficient for balanced trees and less so for skewed trees. This analysis is crucial for understanding the performance implications of using this algorithm, especially when dealing with large or unbalanced trees.

Conclusion

We have decoded the intricacies of verifying Binary Search Trees (BSTs). Isn’t it fascinating how a simple set of rules can define such a powerful data structure? Now, not only can you implement a BST, but you also know how to ensure it stays true to its principles.

If you’re feeling pumped and ready for a challenge, why not try to implement it on LeetCode? It’s the perfect arena to apply what we’ve discussed and even discover new insights.

But don’t stop there! Our “Art Of Coding” blog has more posts delving into all sorts of tree structures. If you’re curious about how trees branch out (pun intended) in the world of algorithms, you’ll definitely want to check those out.

Now go ahead, get your hands dirty with code, and watch your efforts bloom into mastery.

Happy coding!

References

Cracking the Coding Interview: This book is a renowned best-seller and a personal favorite – an essential book for preparing for technical interviews!
Designing Data-Intensive Applications: ‘ is a go-to reference for creating scalable, robust, and high-performance applications!

Is Your Tree a BST? Algorithmic Verification Explained

Introduction