Validate if Tree is BST in DSA Go - Deep Dive

Overview - Validate if Tree is BST

What is it?

A Binary Search Tree (BST) is a special kind of tree where each node has at most two children. For every node, all values in its left subtree are smaller, and all values in its right subtree are larger. Validating if a tree is a BST means checking if this rule holds true for every node in the tree. This helps ensure the tree can be used for fast searching and sorting.

Why it matters

Without knowing if a tree is a BST, we cannot trust its fast search ability. Many programs rely on BSTs to quickly find, add, or remove data. If the tree breaks the BST rules, operations become slow and unreliable, causing delays or errors in software. Validating the tree keeps data organized and efficient.

Where it fits

Before this, you should understand basic trees and binary trees. After learning BST validation, you can explore tree traversals, balanced trees like AVL or Red-Black trees, and advanced search algorithms.

Mental Model

Core Idea

A tree is a BST if every node's left side has smaller values and right side has larger values, all the way down.

Think of it like...

Imagine a library shelf where all books to the left are alphabetically before the current book, and all books to the right come after it. If this order is true for every book, the shelf is perfectly sorted like a BST.

        [Node]
       /      \
  < smaller   > larger
   subtree    subtree

Every node divides its subtree into smaller and larger parts.

Build-Up - 7 Steps

1

Foundation

Understand Binary Tree Structure

Concept: Learn what a binary tree is and how nodes connect.

A binary tree is a structure where each node has up to two children: left and right. Each node holds a value. The tree starts at a root node and branches down. Example: 10 / \ 5 15 Here, 10 is root, 5 is left child, 15 is right child.

Result

You can visualize and represent trees with nodes and links.

Understanding the basic shape and connections of a binary tree is essential before checking any special rules like BST.

2

Foundation

Know BST Property Rules

Concept: Learn the rule that defines a BST: left < node < right.

In a BST, for every node: - All values in the left subtree are less than the node's value. - All values in the right subtree are greater than the node's value. This rule applies recursively to every node in the tree.

Result

You can identify if a tree follows the BST property by checking each node's children.

Knowing this rule is the foundation for validating if a tree is a BST.

3

Intermediate

Simple Recursive Validation Approach

🤔Before reading on: Do you think checking only immediate children is enough to validate a BST? Commit to yes or no.

Concept: Check if each node's immediate children satisfy BST rules recursively.

A naive approach checks if left child < node and right child > node, then recursively checks children. Example in Go: func isBST(node *Node) bool { if node == nil { return true } if node.Left != nil && node.Left.Value >= node.Value { return false } if node.Right != nil && node.Right.Value <= node.Value { return false } return isBST(node.Left) && isBST(node.Right) } This looks correct but misses deeper violations.

Result

This method can wrongly say a tree is BST when it is not.

Understanding this common mistake helps avoid false positives in BST validation.

4

Intermediate

Use Min-Max Range for Validation

🤔Before reading on: Should BST validation consider value ranges from ancestors or just immediate children? Commit to your answer.

Concept: Pass down allowed value ranges to each node to ensure all descendants fit BST rules.

Each node must be within a min and max value range: - Left child must be less than current node's value. - Right child must be greater than current node's value. Example in Go: func validateBST(node *Node, min, max *int) bool { if node == nil { return true } if (min != nil && node.Value <= *min) || (max != nil && node.Value >= *max) { return false } return validateBST(node.Left, min, &node.Value) && validateBST(node.Right, &node.Value, max) } Call with validateBST(root, nil, nil).

Result

This method correctly validates BST by checking all nodes against allowed ranges.

Knowing to track value limits from ancestors ensures no hidden BST violations.

5

Intermediate

Inorder Traversal Validation Method

🤔Before reading on: Does an inorder traversal of a BST produce sorted values? Commit yes or no.

Concept: Use inorder traversal to check if node values appear in strictly increasing order.

Inorder traversal visits nodes in left-root-right order. For BST, this produces sorted values. Algorithm: - Traverse tree inorder. - Keep track of previous node value. - If current node value <= previous, tree is not BST. Example in Go: var prev *int func inorderValidate(node *Node) bool { if node == nil { return true } if !inorderValidate(node.Left) { return false } if prev != nil && node.Value <= *prev { return false } prev = &node.Value return inorderValidate(node.Right) } Call with inorderValidate(root).

Result

If traversal values are sorted, tree is BST; otherwise not.

Using inorder traversal leverages BST's sorted property for a simple validation.

6

Advanced

Validate BST with Duplicate Handling

🤔Before reading on: Should duplicates be allowed on left, right, or not at all in BST? Commit your guess.

Concept: Handle trees where duplicates may appear on one side according to specific rules.

Some BST definitions allow duplicates only on the right or left. Adjust validation accordingly: - For duplicates on right: use >= for right subtree check. - For duplicates on left: use <= for left subtree check. Example modification in Go: func validateBSTWithDup(node *Node, min, max *int, allowEqualRight bool) bool { if node == nil { return true } if min != nil { if allowEqualRight { if node.Value < *min { return false } } else { if node.Value <= *min { return false } } } if max != nil { if allowEqualRight { if node.Value > *max { return false } } else { if node.Value >= *max { return false } } } return validateBSTWithDup(node.Left, min, &node.Value, allowEqualRight) && validateBSTWithDup(node.Right, &node.Value, max, allowEqualRight) } Call with allowEqualRight true or false based on rules.

Result

Validation respects duplicate placement rules, avoiding false negatives or positives.

Knowing how to handle duplicates prevents confusion in real-world BSTs where duplicates exist.

7

Expert

BST Validation in Production Systems

🤔Before reading on: Do you think BST validation is always done at runtime or sometimes during data insertion? Commit your answer.

Concept: Understand when and how BST validation is used in real systems for correctness and performance.

In production, BST validation is often done: - During insertion or deletion to maintain tree integrity. - As a debug or test step to catch corruption. Full tree validation at runtime is costly; incremental checks are preferred. Also, balanced BSTs (AVL, Red-Black) add complexity to validation. Example: Database indexes use BST-like structures and validate on updates. Understanding these patterns helps write efficient, reliable code.

Result

You know when to validate fully, partially, or rely on invariants.

Knowing practical validation strategies prevents performance issues and bugs in real applications.

Under the Hood

BST validation works by checking each node's value against allowed minimum and maximum limits derived from ancestor nodes. This ensures the entire subtree respects the BST ordering, not just immediate children. The process uses recursion, passing down updated limits as it moves left or right. Internally, this prevents violations where a node deep in the left subtree might be greater than the root, which simple child checks miss.

Why designed this way?

The min-max approach was designed to catch subtle BST violations that naive checks miss. Early methods only compared immediate children, which failed for complex trees. Passing value ranges down the tree is a clean, efficient way to enforce global ordering rules. This method balances simplicity and correctness, making it widely adopted.

          [Root Node]
          /         \
   min < node.val < max
       /               \
  Left subtree       Right subtree
  (max updated)      (min updated)

Each recursive call narrows allowed value range.

Myth Busters - 4 Common Misconceptions

Quick: Is checking only immediate children enough to confirm a BST? Commit yes or no.

Common Belief: If each node's left child is smaller and right child is larger, the tree is a BST.

Reality: This is false because deeper descendants can violate BST rules even if immediate children do not.

Why it matters: Relying on this leads to incorrect validation, causing bugs in search or insert operations.

Quick: Does an inorder traversal of any binary tree always produce sorted values? Commit yes or no.

Common Belief: Inorder traversal always gives sorted values regardless of tree type.

Reality: Only BSTs produce sorted values in inorder traversal; other trees do not guarantee this.

Why it matters: Misusing inorder traversal for validation on non-BSTs leads to wrong conclusions.

Quick: Can duplicates appear anywhere in a BST? Commit yes or no.

Common Belief: Duplicates can be anywhere in a BST without breaking rules.

Reality: BST definitions vary, but duplicates must be consistently placed (e.g., always right subtree) or disallowed.

Why it matters: Ignoring duplicate rules causes inconsistent trees and validation errors.

Quick: Is full tree validation always done in production systems? Commit yes or no.

Common Belief: BST validation is always done on the entire tree at runtime.

Reality: Full validation is expensive; production systems often validate incrementally during updates.

Why it matters: Misunderstanding this leads to inefficient code and performance problems.

Expert Zone

1

BST validation must consider integer overflow or data type limits when comparing values in some languages.

2

In concurrent environments, BST validation requires synchronization to avoid race conditions during traversal.

3

Balanced BSTs add extra properties (like height or color) that require additional validation beyond simple ordering.

When NOT to use

Avoid full tree validation in performance-critical systems during runtime; instead, validate during insertions or deletions. For non-BST trees like heaps or tries, use their specific validation methods.

Production Patterns

In databases and file systems, BST validation is integrated with insertion and deletion logic to maintain integrity. Debug builds may include full validation passes. Balanced BSTs require combined validation of ordering and balancing properties.

Connections

Binary Tree Traversals

Builds-on

Understanding inorder traversal is key to one of the simplest BST validation methods.

Balanced Trees (AVL, Red-Black Trees)

Builds-on

BST validation is a foundation before adding complexity of balancing rules in advanced trees.

Sorting Algorithms

Related pattern

BSTs maintain sorted order in their structure, linking tree validation to sorting correctness.

Common Pitfalls

#1 Checking only immediate children for BST property.

Wrong approach:

func isBST(node *Node) bool {
if node == nil {
return true
}
if node.Left != nil && node.Left.Value >= node.Value {
return false
}
if node.Right != nil && node.Right.Value <= node.Value {
return false
}
return isBST(node.Left) && isBST(node.Right)
}

Correct approach:

func validateBST(node *Node, min, max *int) bool {
if node == nil {
return true
}
if (min != nil && node.Value <= *min) || (max != nil && node.Value >= *max) {
return false
}
return validateBST(node.Left, min, &node.Value) && validateBST(node.Right, &node.Value, max)
}

Root cause:

Misunderstanding that BST property applies globally, not just between parent and immediate children.

#2 Ignoring duplicate value rules in BST validation.

Wrong approach:

func validateBST(node *Node, min, max *int) bool {
if node == nil {
return true
}
if (min != nil && node.Value < *min) || (max != nil && node.Value > *max) {
return false
}
return validateBST(node.Left, min, &node.Value) && validateBST(node.Right, &node.Value, max)
}

Correct approach:

func validateBSTWithDup(node *Node, min, max *int, allowEqualRight bool) bool {
if node == nil {
return true
}
if min != nil {
if allowEqualRight {
if node.Value < *min {
return false
}
} else {
if node.Value <= *min {
return false
}
}
}
if max != nil {
if allowEqualRight {
if node.Value > *max {
return false
}
} else {
if node.Value >= *max {
return false
}
}
}
return validateBSTWithDup(node.Left, min, &node.Value, allowEqualRight) &&
validateBSTWithDup(node.Right, &node.Value, max, allowEqualRight)
}

Root cause:

Not accounting for how duplicates are allowed or disallowed in BST definitions.

#3 Performing full tree validation at runtime in performance-critical code.

Wrong approach:

// Validate entire tree on every operation
func validateEveryTime(root *Node) bool {
return validateBST(root, nil, nil)
}

Correct approach:

// Validate only during insert/delete or in debug mode
func insertNode(root *Node, val int) *Node {
// Insert logic with local validation
// Full validation done separately if needed
return root
}

Root cause:

Not understanding the cost of full validation and when it is practical.

Key Takeaways

A BST requires every node's left subtree to have smaller values and right subtree to have larger values, globally.

Simple checks of immediate children are not enough; validation must consider value ranges from ancestors.

Inorder traversal of a BST produces sorted values, which can be used for validation.

Handling duplicates in BSTs requires clear rules and adjusted validation logic.

In real systems, BST validation is often incremental to balance correctness and performance.

Practice

1. What does it mean for a binary tree to be a Binary Search Tree (BST)?

easy

A. All nodes have the same value.

B. Every node has exactly two children.

C. The tree is balanced with equal height on both sides.

D. Every node's left subtree contains values less than the node, and right subtree contains values greater.

Solution

1. Step 1: Understand BST property

   A BST requires that for each node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater.

2. Step 2: Compare options with definition

   Every node's left subtree contains values less than the node, and right subtree contains values greater. matches the BST property exactly, while others describe different tree properties.

3. Final Answer:

   Every node's left subtree contains values less than the node, and right subtree contains values greater. -> Option D

4. Quick Check:

   BST property = Every node's left subtree contains values less than the node, and right subtree contains values greater. [OK]

Hint: BST means left < node < right for every node [OK]

Common Mistakes:

• Confusing BST with balanced tree
• Thinking all nodes must have two children
• Assuming all values are equal

2. Which Go function signature correctly represents a function to check if a binary tree is a BST?

easy

A. func isBST(root *Node) bool

B. func isBST(root Node) int

C. func checkBST(root *Node) string

D. func validateBST(root Node) void

Solution

1. Step 1: Identify correct parameter and return types

   The function should accept a pointer to the root node (to avoid copying) and return a boolean indicating if the tree is BST.

2. Step 2: Match with options

   func isBST(root *Node) bool matches this: it takes *Node and returns bool. Others have wrong parameter types or return types.

3. Final Answer:

   func isBST(root *Node) bool -> Option A

4. Quick Check:

   Pointer input + bool output = func isBST(root *Node) bool [OK]

Hint: Use pointer receiver and bool return for BST check [OK]

Common Mistakes:

• Passing Node by value instead of pointer
• Returning int or string instead of bool
• Using void (no return) for validation function

3. Given the following Go code, what will be the output?

package main

import "fmt"

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

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

func isBST(root *Node) bool {
    return isBSTUtil(root, -1000, 1000)
}

func main() {
    root := &Node{Val: 10}
    root.Left = &Node{Val: 5}
    root.Right = &Node{Val: 15}
    root.Right.Left = &Node{Val: 6}
    root.Right.Right = &Node{Val: 20}
    fmt.Println(isBST(root))
}

medium

A. false

B. true

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Trace tree values against BST rules

   The node with value 6 is in the right subtree of 10 but less than 10, violating BST property.

2. Step 2: Check isBSTUtil logic

   isBSTUtil checks if node.Val is within (min, max). For node 6, min=10, max=15, but 6 <= 10 fails the condition, returning false.

3. Final Answer:

   false -> Option A

4. Quick Check:

   6 in right subtree < 10 = false [OK]

Hint: Check subtree values against min/max bounds [OK]

Common Mistakes:

• Ignoring subtree value constraints
• Assuming all nodes in right subtree are greater than root only
• Not updating min/max bounds during recursion

4. The following Go function is intended to check if a binary tree is a BST, but it has a bug. What is the bug?

func isBST(node *Node) bool {
    if node == nil {
        return true
    }
    if node.Left != nil && node.Left.Val > node.Val {
        return false
    }
    if node.Right != nil && node.Right.Val < node.Val {
        return false
    }
    return isBST(node.Left) && isBST(node.Right)
}

medium

A. It does not handle nil nodes correctly.

B. It only compares immediate children, missing deeper subtree violations.

C. It uses wrong comparison operators for BST.

D. It causes infinite recursion.

Solution

1. Step 1: Analyze comparison logic

   The function compares only node.Left.Val and node.Right.Val with node.Val, ignoring entire subtree values.

2. Step 2: Understand BST violation cases

   A violation can occur deeper in subtrees, e.g., a left subtree node greater than root, which this function misses.

3. Final Answer:

   It only compares immediate children, missing deeper subtree violations. -> Option B

4. Quick Check:

   Check all subtree nodes, not just immediate children [OK]

Hint: Check entire subtree ranges, not just direct children [OK]

Common Mistakes:

• Checking only immediate children values
• Not passing min/max bounds in recursion
• Assuming local checks guarantee global BST

5. You want to validate if a binary tree is a BST but the tree nodes can have duplicate values. Which modification to the standard BST validation logic is correct to allow duplicates only on the right subtree?

hard

A. Change the condition to allow node.Val <= max for left subtree and node.Val > max for right subtree.

B. Allow duplicates only if node.Val >= min for left subtree and node.Val < max for right subtree.

C. Allow duplicates only if node.Val > min for left subtree and node.Val <= max for right subtree.

D. Allow duplicates on both sides without changing conditions.

Solution

1. Step 1: Understand duplicate placement in BST

   Duplicates allowed only on right means left subtree nodes must be strictly less than node.Val, right subtree nodes can be equal or greater.

2. Step 2: Adjust min/max conditions accordingly

   Change violation check to (node.Val <= min || node.Val > max), enforcing node.Val > min && node.Val <= max. This allows equality to max (parent.Val in right calls) but enforces > min (parent.Val in left calls).

3. Final Answer:

   Allow duplicates only if node.Val > min for left subtree and node.Val <= max for right subtree. -> Option C

4. Quick Check:

   > min && <= max = duplicates on right only [OK]

Hint: Use > min && <= max to allow duplicates on right [OK]

Common Mistakes:

• Allowing duplicates on left subtree
• Not adjusting inequality signs properly
• Allowing duplicates on both sides without rules