JavaScript Solution O(n) - Recursive InOrderTraversal


  • 0
    K

    This is a relatively simple approach. An in-order traversal will give us a sorted array if it is a valid BST. So we are going to create an array using in-order traversal. Then we just need to check if the array is sorted, and if it is, we have a valid BST.

    /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * @param {TreeNode} root
     * @return {boolean}
     */
    var isValidBST = function(root) {
        var inOrderArray = [];
        
        inOrderTraversal(root, function(val) {
            inOrderArray.push(val);
        });
    
        for (var i = 1; i < inOrderArray.length; i++) {
            if (inOrderArray[i] <= inOrderArray[i-1]) return false;
        }
        
        return true;
    };
    
    function inOrderTraversal (node, fn) {
        if (!node) {
            return;
        }
        
        inOrderTraversal(node.left, fn);
        fn(node.val);
        inOrderTraversal(node.right, fn);
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.