Validate Binary Search Tree

1. Problem Description

Given a binary tree, determine whether it is a valid binary search tree.

A binary search tree has the following properties:

The left subtree of a node contains only values less than the current node. The right subtree contains only values greater than the current node. Both the left and right subtrees must themselves be binary search trees.

2. Approach

1. Approach 1
   • Convert the inorder traversal to an array
   • Check whether the array is strictly increasing
2. Approach 2
   • During inorder traversal, determine whether the current node is greater than the previous inorder node

3. Implementation

3.1. Inorder Traversal

func isValidBST(root *TreeNode) bool {
	if root == nil {
		return true
	}

	res := make([]int, 0)
	midOrder(root, &res)
	for i := 0; i < len(res)-1; i++ {
		if res[i] >= res[i+1] {
			return false
		}
	}

	return true
}

func midOrder(root *TreeNode, res *[]int) {
	if root == nil {
		return
	}

	midOrder(root.Left, res)
	*res = append(*res, root.Val)
	midOrder(root.Right, res)
}

3.2. Record the Previous Value During Traversal

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
    pre := &TreeNode{Val:math.MinInt64}
    return dfs(root, &pre)
}

func dfs(root *TreeNode, pre **TreeNode) bool {
    if root == nil {
        return true
    }

    if flag := dfs(root.Left, pre); !flag {
        return false
    }
    if (*pre).Val >= root.Val {
        return false
    }
    *pre = root
    if flag :=  dfs(root.Right, pre); !flag {
        return false
    }
    return true
}

4. References

• Validate Binary Search Tree - LeetCode