Skip to content

98.validate-binary-search-tree.md

Latest commit

 

History

History
119 lines (108 loc) · 3.34 KB

98.validate-binary-search-tree.md

File metadata and controls

119 lines (108 loc) · 3.34 KB

98. Validate Binary Search Tree

Clarification Questions

  • Is the tree a BST if we have two nodes with the same value?

Test Cases

Normal Cases

Input: 
    2
   / \
  1   3 
Output: true

Input: 
     5
    / \
   1   4
Output: false

Edge / Corner Cases

  • The tree contains the same values.
Input: 
    2
   / \
  2   2

    5
   / \
  1   6
     / \
    5   7
Output: false
  • The subtrees are valid, but the whole tree is not valid.
Input:
     5               5
    / \            /   \
   1   6          3     6
      / \        / \   
     3   7      1   7
Output: false, because 3 is in the right subtree of 5 but it is less than 5. Or 7 is in the subtree that is less than 5.

Inorder Traversal (Recursive)

The inorder traversal is in ascending order for a BST. We can traverse the tree in inorder and check if the traversal is in ascending order.

fun isValidBST(root: TreeNode?): Boolean {
    if (root == null) return true        
    
    val traversal = mutableListOf<Int>()
    inorderTraversal(root, traversal)
    
    if (traversal.size == 1) return true
    else {
        for (i in 1 until traversal.size) {
            if (traversal[i - 1] >= traversal[i]) return false
        }
        return true
    }
}

private fun inorderTraversal(root: TreeNode?, results: MutableList<Int>) {
    if (root?.left != null) inorderTraversal(root.left!!, results)
    if (root != null) results.add(root.`val`)
    if (root?.right != null) inorderTraversal(root.right!!, results)
}
  • Time Complexity: O(n).
  • Space Complexity: O(n).

Inorder Traversal (Iterative)

The same idea as the recursive solution above.

fun isValidBST(root: TreeNode?): Boolean {
    if (root == null) return true
    val stack = Stack<TreeNode>()
    var node: TreeNode? = root
    var previous: Int? = null
    while (!stack.isEmpty() || node != null) {
        while (node != null) {
            stack.push(node)
            node = node.left
        }
        node = stack.pop()
        if (previous != null && previous >= node.`val`) return false
        previous = node.`val`
        node = node.right
    }
    return true
}
  • Time Complexity: O(n).
  • Space Complexity: O(n).

Recursion

For any node in BST, the the value of current node is greater than all the values in left subtree and less than all the values in right subtree. We can use this property to validate the BST:

        root
        /  \
    left    right
  • In each function call, we track the minimum and maximum value, and verify if the current value is in the range.
  • To check left subtree, the current value becomes the maximum value because the current value is always greater than the left subtree.
  • To check right subtree, the current value becomes the minimum value because the current value is always less than the right subtree.
fun isValidBST(root: TreeNode?): Boolean {
    return isValidBST(root, Int.MIN_VALUE, Int.MAX_VALUE)
}

fun isValidBST(root: TreeNode?, min: Int, max: Int): Boolean {
    if (root == null) return true
    return min < root.`val` && root.`val` < max && isValidBST(root.left, min, root.`val`) && isValidBST(root.right, root.`val`, max)
}
  • Time Complexity: O(n).
  • Space Complexity: O(h), the wost case is O(n) for skewed tree.