arcbjorn

thoughtbook

Sunday, March 5, 2023

Validate binary search tree

Leetcode 98 problem.

Go

  • Time complexity: O(n)O(n) - n is a number of nodes
  • Auxiliary space: O(d)O(d) - d is a depth of a binary tree
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 
func isValidBST(root *TreeNode) bool {
    return checkWithMinMax(root, -1<<63, 1<<63-1)
}

func checkWithMinMax(root *TreeNode, left, right int) bool {
    if root == nil {
        return true
    }

    if root.Val >= right || root.Val <= left {
        return false
    }

    isValidLeft := checkWithMinMax(root.Left, left, root.Val)
    isValidRight := checkWithMinMax(root.Right, root.Val, right)

    return isValidLeft && isValidRight
}
Creative Commons Licence