Validate if Tree is BST in DSA Go

Mental Model

A binary search tree (BST) has nodes arranged so that left children are smaller and right children are bigger than the parent node.

Analogy: Imagine a family tree where every child on the left side is younger than their parent, and every child on the right side is older, keeping the order clear.

      5
     / \
    3   7
   / \   \
  2   4   8

Dry Run Walkthrough

Input: Tree: 5 with left child 3 and right child 7; 3 has children 2 and 4; 7 has right child 8

Goal: Check if this tree follows BST rules where left < parent < right for every node

Step 1: Start at root node 5, set allowed range as (-∞, +∞)

Node=5, range=(-∞, +∞)

Why: We begin with no limits for the root value

Step 2: Check left child 3 with range (-∞, 5)

Node=3, range=(-∞, 5)

Why: Left child must be less than parent 5

Step 3: Check left child 2 with range (-∞, 3)

Node=2, range=(-∞, 3)

Why: Left child of 3 must be less than 3

Step 4: 2 has no children, return true and go back to 3

Node=2 leaf, valid

Why: Leaf nodes are valid by default

Step 5: Check right child 4 of 3 with range (3, 5)

Node=4, range=(3, 5)

Why: Right child of 3 must be greater than 3 and less than 5

Step 6: 4 has no children, return true and go back to 3

Node=4 leaf, valid

Why: Leaf nodes are valid by default

Step 7: Left subtree of 5 is valid, check right child 7 with range (5, +∞)

Node=7, range=(5, +∞)

Why: Right child must be greater than parent 5

Step 8: Check right child 8 of 7 with range (7, +∞)

Node=8, range=(7, +∞)

Why: Right child of 7 must be greater than 7

Step 9: 8 has no children, return true and go back to 7

Node=8 leaf, valid

Why: Leaf nodes are valid by default

Step 10: Right subtree of 5 is valid, whole tree is BST

Tree valid as BST

Why: All nodes satisfy BST conditions

Result:

2 -> 3 -> 4 -> 5 -> 7 -> 8 (inorder traversal) confirms BST

Annotated Code

DSA Go

package main

import (
	"fmt"
	"math"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func isValidBST(root *TreeNode) bool {
	return validate(root, math.Inf(-1), math.Inf(1))
}

func validate(node *TreeNode, min, max float64) bool {
	if node == nil {
		return true
	}
	val := float64(node.Val)
	if val <= min || val >= max {
		return false
	}
	// Check left subtree with updated max
	if !validate(node.Left, min, val) {
		return false
	}
	// Check right subtree with updated min
	if !validate(node.Right, val, max) {
		return false
	}
	return true
}

func main() {
	root := &TreeNode{Val: 5}
	root.Left = &TreeNode{Val: 3}
	root.Right = &TreeNode{Val: 7}
	root.Left.Left = &TreeNode{Val: 2}
	root.Left.Right = &TreeNode{Val: 4}
	root.Right.Right = &TreeNode{Val: 8}

	fmt.Println(isValidBST(root))
}

return validate(root, math.Inf(-1), math.Inf(1))

start validation with infinite range for root

if node == nil { return true }

empty node is valid BST by definition

if val <= min || val >= max { return false }

check if current node violates min/max range

if !validate(node.Left, min, val) { return false }

validate left subtree with updated max limit

if !validate(node.Right, val, max) { return false }

validate right subtree with updated min limit

Output

true

Complexity Analysis

Time: O(n) because we visit each node once to check BST property

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to inorder traversal checking sorted order, this method checks constraints directly during traversal, saving extra space for storing values

Edge Cases

Empty tree

Returns true because empty tree is a valid BST

DSA Go

if node == nil {
	return true
}

Single node tree

Returns true because single node satisfies BST rules

DSA Go

if node == nil {
	return true
}

Tree with duplicate values

Returns false because BST does not allow duplicates (<= or >= fails)

DSA Go

if val <= min || val >= max {
	return false
}

When to Use This Pattern

When you need to confirm if a binary tree follows the BST rules, use range limits during recursion to validate each node's value fits between allowed min and max.

Common Mistakes

Mistake: Only checking immediate children values without considering entire subtree range
Fix: Pass down min and max limits to ensure all descendants satisfy BST property

Summary

Checks if a binary tree is a valid binary search tree by ensuring all nodes fit within value ranges.

Use when you want to verify the BST property in a binary tree structure.

The key insight is to track allowed min and max values for each node during recursion.