Solving Validate Binary Search Tree in Go: Step-by-Step Guide

The "Validate Binary Search Tree" problem is one of the most frequently asked questions in coding interviews and a fundamental exercise for understanding tree data structures. In this tutorial, we will walk through what a Binary Search Tree (BST) is, why validating it matters, and how to implement an efficient solution in Go using multiple approaches.

What Is a Binary Search Tree?

A Binary Search Tree is a binary tree where every node follows a strict ordering property: for any given node, all values in its left subtree must be strictly less than the node's value, and all values in its right subtree must be strictly greater than the node's value. This property must hold for every node in the tree, not just the root.

Here is a simple tree node definition in Go that we will use throughout this tutorial:

package main

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

It is important to note that the BST property is a global constraint. A common mistake is to only check that the immediate left child is smaller and the immediate right child is larger. That is not enough, because a deeply nested node could still violate the ordering relative to an ancestor higher up in the tree.

Why Validating a BST Matters

Binary Search Trees power many real-world systems because they allow O(log n) average-case lookups, insertions, and deletions. However, those performance guarantees only hold when the tree is actually a valid BST. If the structure becomes corrupted through buggy insertion or deletion logic, operations can silently return incorrect results or degrade to O(n) performance.

Data integrity: Databases and indexing systems rely on BST-like structures to maintain sorted data.
Algorithm correctness: Many tree algorithms assume the BST property and produce wrong results otherwise.
Interview readiness: This problem tests your understanding of recursion, tree traversal, and boundary propagation.
Bug detection: Validating a BST is a useful sanity check after implementing custom insertion or deletion logic.

Understanding the Problem Statement

Given the root of a binary tree, return true if it is a valid BST, and false otherwise. A valid BST is defined as follows:

The left subtree of a node contains only nodes with values less than the node's value.
The right subtree of a node contains only nodes with values greater than the node's value.
Both the left and right subtrees must also be valid BSTs.

Consider this tree, which looks valid at a glance but is actually invalid:

Although 3 is less than its parent 6, it is also less than the root 5, which means it cannot live in the right subtree of 5. This is why we need to track valid ranges as we traverse down the tree.

Approach 1: Recursive Validation With Bounds

The cleanest way to solve this problem is to pass down a valid range (min, max) as we recurse. When we go left, the upper bound becomes the current node's value. When we go right, the lower bound becomes the current node's value. If any node falls outside its allowed range, the tree is invalid.

Implementation

package main

import (
    "fmt"
    "math"
)

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

func isValidBST(root *TreeNode) bool {
    return validate(root, math.MinInt64, math.MaxInt64)
}

func validate(node *TreeNode, min, max int) bool {
    if node == nil {
        return true
    }
    if node.Val <= min || node.Val >= max {
        return false
    }
    return validate(node.Left, min, node.Val) &&
        validate(node.Right, node.Val, max)
}

func main() {
    // Build the invalid example tree from above
    root := &TreeNode{Val: 5}
    root.Left = &TreeNode{Val: 4}
    root.Right = &TreeNode{Val: 6}
    root.Right.Left = &TreeNode{Val: 3}
    root.Right.Right = &TreeNode{Val: 7}

    fmt.Println("Is valid BST?", isValidBST(root)) // false

    // Build a valid BST
    valid := &TreeNode{Val: 5}
    valid.Left = &TreeNode{Val: 3}
    valid.Right = &TreeNode{Val: 7}
    valid.Left.Left = &TreeNode{Val: 1}
    valid.Left.Right = &TreeNode{Val: 4}

    fmt.Println("Is valid BST?", isValidBST(valid)) // true
}

How It Works

Each recursive call narrows the acceptable range for the subtree. The root starts with the widest possible range. As we descend, the bounds tighten based on the ancestors we have visited. This guarantees that every node is checked against all of its relevant ancestors, not just its immediate parent.

The time complexity is O(n) because we visit every node exactly once. The space complexity is O(h) where h is the height of the tree, due to the recursion stack. In a balanced tree this is O(log n), but in the worst case of a degenerate tree it becomes O(n).

Approach 2: In-Order Traversal

An in-order traversal of a valid BST visits nodes in strictly increasing order. We can exploit this property by traversing the tree in-order and checking that each value is greater than the previous one. If we ever find a value that is not strictly greater, the tree is invalid.

Implementation

package main

import (
    "fmt"
    "math"
)

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

func isValidBSTInOrder(root *TreeNode) bool {
    prev := math.MinInt64
    var inorder func(node *TreeNode) bool
    inorder = func(node *TreeNode) bool {
        if node == nil {
            return true
        }
        if !inorder(node.Left) {
            return false
        }
        if node.Val <= prev {
            return false
        }
        prev = node.Val
        return inorder(node.Right)
    }
    return inorder(root)
}

func main() {
    valid := &TreeNode{Val: 5}
    valid.Left = &TreeNode{Val: 3}
    valid.Right = &TreeNode{Val: 7}
    valid.Left.Left = &TreeNode{Val: 1}
    valid.Left.Right = &TreeNode{Val: 4}

    fmt.Println("Is valid BST?", isValidBSTInOrder(valid)) // true
}

Why This Works

In-order traversal visits the left subtree, then the node itself, then the right subtree. For a BST, this naturally produces a sorted sequence. By keeping track of the previously visited value in a closure variable, we can detect any out-of-order element in a single pass. This approach also runs in O(n) time and O(h) space.

One subtle advantage of the in-order approach is that it can short-circuit early. As soon as we detect a violation, we stop traversing, which can save work on large invalid trees.

Approach 3: Iterative In-Order Traversal

If you want to avoid recursion entirely, perhaps to prevent stack overflow on very deep trees, you can use an explicit stack to perform the in-order traversal iteratively. The logic is the same: track the previous value and ensure strict increase.

package main

import (
    "fmt"
    "math"
)

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

func isValidBSTIterative(root *TreeNode) bool {
    var stack []*TreeNode
    prev := math.MinInt64
    curr := root

    for curr != nil || len(stack) > 0 {
        // Go as far left as possible
        for curr != nil {
            stack = append(stack, curr)
            curr = curr.Left
        }
        // Pop the top node
        curr = stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        if curr.Val <= prev {
            return false
        }
        prev = curr.Val
        curr = curr.Right
    }
    return true
}

func main() {
    valid := &TreeNode{Val: 5}
    valid.Left = &TreeNode{Val: 3}
    valid.Right = &TreeNode{Val: 7}

    fmt.Println("Is valid BST?", isValidBSTIterative(valid)) // true
}

This iterative version has the same O(n) time and O(h) space complexity, but it gives you full control over the traversal and avoids any recursion depth limits.

Best Practices

Use Strict Inequality

Remember that BST validation requires strict inequality. Duplicate values are not allowed in a standard BST. Using <= or >= in your comparisons ensures duplicates are correctly rejected.

Handle Integer Boundaries Carefully

If your tree can contain values at the extreme ends of the integer range, using math.MinInt64 and math.MaxInt64 as initial bounds may not be safe. A more robust approach is to use pointers or a separate boolean flag to indicate "no bound":

func validate(node *TreeNode, min, max *int) bool {
    if node == nil {
        return true
    }
    if min != nil && node.Val <= *min {
        return false
    }
    if max != nil && node.Val >= *max {
        return false
    }
    return validate(node.Left, min, &node.Val) &&
        validate(node.Right, &node.Val, max)
}

func isValidBST(root *TreeNode) bool {
    return validate(root, nil, nil)
}

This version correctly handles trees containing math.MinInt64 or math.MaxInt64 as actual node values.

Choose the Right Approach for the Context

Use the recursive bounds approach when you want the clearest, most readable code that directly mirrors the problem definition.
Use the in-order traversal approach when you want to leverage the sorted-sequence property and potentially short-circuit early.
Use the iterative approach when dealing with very deep trees where recursion could cause stack overflow.

Test Edge Cases Thoroughly

Always test your solution against these edge cases:

An empty tree (nil root) — should return true.
A single-node tree — should return true.
A tree with duplicate values — should return false.
A tree where a deep node violates an ancestor's constraint but not its parent's.
A tree containing math.MinInt64 or math.MaxInt64.

Avoid the Common Pitfall

The most frequent mistake is checking only immediate children instead of the full valid range. This naive approach fails on trees like the invalid example shown earlier:

// WRONG: only checks immediate children
func isValidBSTNaive(root *TreeNode) bool {
    if root == nil {
        return true
    }
    if root.Left != nil && root.Left.Val >= root.Val {
        return false
    }
    if root.Right != nil && root.Right.Val <= root.Val {
        return false
    }
    return isValidBSTNaive(root.Left) && isValidBSTNaive(root.Right)
}

This function would incorrectly return true for the tree where 3 sits in the right subtree of 5. Always propagate bounds down the recursion.

Conclusion

Validating a Binary Search Tree is a deceptively simple problem that rewards a deep understanding of tree structure and recursion. By propagating valid ranges down the tree or leveraging the sorted nature of in-order traversal, you can build a correct and efficient solution in Go. The recursive bounds approach is the most intuitive and directly mirrors the problem definition, while the in-order approaches offer elegant alternatives that can short-circuit early. Whichever method you choose, remember to use strict inequality, handle integer boundaries carefully, and test against edge cases including empty trees, single nodes, duplicates, and deeply nested violations. Mastering this problem will strengthen your grasp of tree algorithms and prepare you well for more advanced challenges involving balanced trees, range queries, and self-adjusting structures.