The title

Interview question 04.05. Legal binary search tree

Implement a function that checks if a binary tree is a binary search tree.

Example 1:

Input: 2 / \ 1 3 Output: trueCopy the code

Example 2:

Input: 5 / \ 1 4 / \ 3 6 Output: false Description: Input: [5,1,4, NULL, NULL,3,6] The root node has a value of 5, but its right child node has a value of 4.Copy the code

Idea 1:

Preorder Traversal of binary tree (recursive method)

We can break this down into smaller problems,

  • So for each node, it has to conform to the binary search tree has a range of values, let’s say the range is lower,upper.

  • It itself is in this range, and its left and right subtrees are binary search trees, so it and its children are binary search trees

  • Then we can analyze its left child node and right child node respectively, directly up to the leaf node

  • If the child node of the leaf node is empty, then it also conforms to the binary search tree, so there is a condition for jumping recursion, which is root==null, then return true

  • At the beginning, lower and upper are -infinity and Infinity for the root node, so the starting conditions are there

The code is as follows:

/ * * *@param {TreeNode} root
 * @return {boolean}* /
var isValidBST = function(root) {
    return isBST(root,-Infinity.Infinity)};function isBST(root,lower,upper){
    if(! root)return true;
    if(root.val<=lower || root.val >= upper) return false;
    return isBST(root.left,lower,root.val) && isBST(root.right,root.val,upper)
}
Copy the code

Complexity analysis:

Time complexity: O(n), where n is the number of nodes in the binary tree, because each node is traversed once.

Space complexity: O(n), recursive function In the process of recursion, need to allocate additional stack space for each layer, then the space complexity is proportional to the height of the binary tree, in the worst case, the binary tree is a linked list, then the height is N.

Idea 2:

For a binary search tree, the result of a middle-order traversal happens to be an increasing sequence, so we can start with this idea.

  • If the current value is less than the next value, it is the binary search tree. Otherwise not.

The code is as follows:

function isValidBST (root) {
    let stack = [];
    let prev = -Infinity;

    while (stack.length || root) {
        while (root) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        // If the value of the node is less than or equal to the previous prev, it is not a binary search tree
        if (root.val <= prev) {
            return false;
        }
        prev = root.val;
        root = root.right;
    }
    return true;
}
Copy the code