Search⌘ K
Home
Courses
Data Structures & Algorithms In Go

Solution Review: Is It a BST?

Explore different techniques to determine whether a binary tree qualifies as a Binary Search Tree. Learn to implement recursive checks using node value ranges and in-order traversal to verify BST properties efficiently in Go. Understand the trade-offs in time and space complexity for each method.

We'll cover the following...

Solution

We’ll check the following conditions at each node:

  • The maximum value of the left subtree is smaller than the value of the current node.
  • The minimum value of the right subtree is greater than the current node.

If these conditions are fulfilled, then the given binary tree is a BST. The following code demonstrates this approach.

Go (1.6.2)
package main
import "fmt"
func IsBST(root *Node) bool {
    if root == nil {
        return true
    }
    if root.left != nil && FindMax(root.left).value > root.value {
        return false
    }
    if root.right != nil && FindMin(root.right).value <= root.value {
        return false
    }
    
    return (IsBST(root.left) && IsBST(root.right))
}
/* Testing Code */
func main() {
    arr := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    t := CreateBinarySearchTree(arr)
    fmt.Println(IsBST(t.root));
}

Here the lines 8–13 check the aforementioned conditions with the help of helper functions FindMin() and FindMax() given in the tree.go file. Line 15 sends recursive calls to the left and right subtrees of the current node.

Note: Although the above solution is correct, it is inefficient because the same tree nodes are traversed ...