Validate Binary Search Tree

Validate Binary Search Tree - LeetCodeLeetCode

Problem

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 1:

Input: root = [2,1,3]
Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

Pseudocode

- use properties of BST to validate that left and right child are following rules

Solution

var isValidBST = function (root) {
  function walk(root, minVal, maxVal) {
    // base condition
    if (!root) {
      return true;
    }

    // pre
    if (root.val <= minVal || root.val >= maxVal) {
      return false;
    }
    // recurse

    // left node can't be larger than parent node
    // right node must be larger than parent node
    return (
      walk(root.left, minVal, root.val) && walk(root.right, root.val, maxVal)
    );
    // post
  }

  return walk(root, -Infinity, Infinity);
};

Time and Space Complexity

Time

• What did the code do

• Total -

Space

• What did the code do

• Total -