## Question

>[Leetcode.98 Validate Binary Search Tree
](https://leetcode.com/problems/validate-binary-search-tree/)

<br>

:::info
:::spoiler *Optimal Space & Time Complexity*
<br>

- Time complexity: O()
- Space complexity: O()

:::

<br>

## Thoughts & Solutions

### YC
:::spoiler Code

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */

// Time: `O(n)`, where `n` is the number of nodes in the binary tree.
// Space: `O(n)`, where `n` is the height of the binary tree in the worst-case scenario.

var isValidBST = function(root, min = Number.NEGATIVE_INFINITY, max = Number.POSITIVE_INFINITY) {
    if(!root) return true;
    
    if(min < root.val && root.val < max) return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);

    return false;
};

:::

<hr/>

### Sol

:::spoiler Code

var isValidBST = function(root) {
    function isValid (min, node, max) {
        if(!node) return true;
        if(!(min < node.val && node.val< max)) return false;
        return isValid(min, node.left, node.val) &&  isValid(node.val, node.right, max)
    }
    return isValid(-Infinity, root, Infinity)
};

:::

<hr/>

### 東
"In order" depth first tree traversal of a Binary Search Tree should output node value increasingly


:::spoiler Code

// Time O(n) | Space O(h)
// n is the number of nodes
// h is the height of the tree

var isValidBST = function(root) {
    let prevVal = -Infinity;
    let isValid = true;
    const inOrderTraversal = (node) => {
        if(node && isValid) {
            inOrderTraversal(node.left);
            
            if(prevVal >= node.val) {
                isValid = false;
            }
            prevVal = node.val;
            
            inOrderTraversal(node.right);
        }
    }
    
    inOrderTraversal(root);
    
    return isValid;
};

:::

<hr/>

### Jessie

:::spoiler Code

var isValidBST = function (root) {

    //  BST 特性 left < current < right (包括所有後代都要比 current 大或小)

    if (!root) return true;

    const queue = [];

    //  待驗證的放進 queue 並記錄 max & min
    queue.push({ node: root, max: 2 ** 31, min: -(2 ** 31 + 1) });

    //  當 queue 還有東西要驗證時，持續執行到沒東西需要驗證為止, 或是檢查到錯誤的時候終止
    while (queue.length > 0) {
        const { node, max, min } = queue.pop();

        //  驗證失敗的情況終止迴圈
        if (node.val >= max || node.val <= min) return false;

        //  待驗證的放進 queue 並記錄 max & min
        if (node.right) queue.push({ node: node.right, max: max, min: node.val });
        if (node.left) queue.push({ node: node.left, max: node.val, min: min });
    }

    return true;
};

:::

<hr/>

### 皮皮

:::spoiler Code

:::

<hr/>

### Howard

:::spoiler Code

:::

<hr/>

<br>

## Live Coding

:::spoiler (name)

// write your code here

:::