Solution Review: Is It a BST?

Let’s take a detailed look at the previous challenge’s solution.

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.

Press + to interact
main.go
tree.go
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 ...

Get hands-on with 1400+ tech skills courses.