NUHMAN.com

Introduction

LeetCode 98: Validate Binary Search Tree is a problem where you are asked to determine if a given binary tree is a valid binary search tree (BST). A binary search tree is valid if it satisfies the following conditions:

1. The left subtree of a node contains only nodes with values less than the node’s value.
2. The right subtree of a node contains only nodes with values greater than the node’s value.
3. Both the left and right subtrees must also be binary search trees.

In this problem, you will implement an algorithm to check if a binary tree is a valid binary search tree.

Problem Statement

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Example:

go

Input: root = [2,1,3]
Output: true
Explanation: The given tree is a valid BST.

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The given tree is not a valid BST.
Explanation: The root node's value is 5 but its right child's value is 4, which is less than 5.

Approach:

Recursive Approach with Range Checking

To validate a binary search tree, we can use a recursive approach. The key idea is that for each node in the tree, we need to ensure that its value is within a valid range. We maintain a range for each node: the value of the node must be greater than the lower bound and less than the upper bound.

Steps:

1. Start from the root node.
2. Recursively check the left and right subtrees:

• For the left subtree, the upper bound is the value of the current node.
• For the right subtree, the lower bound is the value of the current node.

1. Check the current node:

• If the node’s value is within the valid range, we proceed to check its left and right subtrees.

1. Base Case:

• If the node is null, it is considered valid by definition.

This solution ensures that every node’s value is within the correct range, and thus the tree satisfies the properties of a binary search tree.

Go Implementation

Recursive Solution

go

package main

import "math"

// TreeNode represents the structure of a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// isValidBST is a function to validate if a tree is a valid binary search tree.
func isValidBST(root *TreeNode) bool {
    return isValidBSTHelper(root, math.MinInt64, math.MaxInt64)
}

// Helper function that validates the BST recursively.
func isValidBSTHelper(node *TreeNode, low, high int) bool {
    // Base case: if the node is null, it's valid by definition.
    if node == nil {
        return true
    }
    
    // The current node's value must be within the range (low, high).
    if node.Val <= low || node.Val >= high {
        return false
    }

    // Recursively check the left and right subtrees with updated ranges.
    return isValidBSTHelper(node.Left, low, node.Val) && isValidBSTHelper(node.Right, node.Val, high)
}

Explanation:

1. TreeNode Structure:

• The TreeNode structure is defined with three fields: Val (the value of the node), Left (pointer to the left child), and Right (pointer to the right child).

1. isValidBST Function:

• This function serves as the entry point. It calls the helper function isValidBSTHelper with the initial range set to the minimum and maximum integer values (math.MinInt64 and math.MaxInt64), which represent the allowed range for the root node.

1. isValidBSTHelper Function:

• The helper function performs the actual recursion:
• If the node is nil, return true because an empty subtree is trivially a valid BST.
• If the node’s value is outside the allowed range (i.e., it is less than or equal to low or greater than or equal to high), return false since it violates the BST property.
• Recursively check the left subtree with the updated upper bound (node.Val) and the right subtree with the updated lower bound (node.Val).

1. Recursion Flow:

• For each node, the left child must have a value strictly less than the current node's value, and the right child must have a value strictly greater.
• This recursive process ensures that each subtree adheres to the BST property.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(h)

Where:

• n is the number of nodes in the binary tree.
• h is the height of the binary tree.

Time Complexity:

• We visit each node exactly once, so the time complexity is O(n), where n is the number of nodes in the tree.

Space Complexity:

• The space complexity depends on the height of the tree due to the recursion stack. In the worst case (a skewed tree), the space complexity is O(n), but for a balanced tree, the space complexity is O(h), where h is the height of the tree.

Edge Cases

1. Empty Tree:

• Input: root = nil
• Output: true
• Explanation: An empty tree is considered a valid BST by definition.

1. Single Node Tree:

• Input: root = [5]
• Output: true
• Explanation: A single-node tree is trivially a valid BST.

1. Left and Right Subtree Violations:

• Input: root = [10, 5, 15, null, null, 6, 20]
• Output: false
• Explanation: The right child of the node 10 has a value 6, which is less than 10, violating the BST property.

Conclusion

LeetCode 98: Validate Binary Search Tree is a fundamental problem in binary tree manipulation that can be solved efficiently with a recursive approach using range checking. By maintaining valid ranges for each node during the traversal, we can ensure that the tree adheres to the binary search tree properties.

This approach has a time complexity of O(n) and space complexity of O(h), where n is the number of nodes and h is the height of the tree, making it an optimal solution for this problem.