Binary tree It is well known that binary search trees satisfy the following characteristics:

The left subtree of a node contains only numbers less than the current node

The right subtree of a node only contains numbers greater than the current node

All left and right subtrees must themselves also be binary search trees

Binary search tree is also called binary sort tree. The result of middle-order traversal binary search tree is an incremental traversal.

The establishment of binary search tree

Related Topics:Leetcode 108. Convert an ordered array to a binary search tree[medium]

So how do you turn an ordered array into a binary search tree?

The root node of each branch of the binary search tree is its intermediate value. According to this feature, the binary method is used to transform the ordered array into a binary search tree.

Const sortedArrayToBST = nums => {// boundary conditionsif (nums.length === 0) {
        return null;
    } 
    if (nums.length === 1) {
        returnnew TreeNode(nums[0]); } // round down to get the middle valuelet mid = Math.floor(nums.length / 2);
    letroot = new TreeNode(nums[mid]); Root. left = sortedArrayToBST(nums.slice(0, mid)); root.right = sortedArrayToBST(nums.slice(mid + 1));return root;
};
Copy the code

Next we verify that the next tree satisfies the binary search tree.

Verify binary search tree

Related Topics:Leetcode 98. Validate binary search trees[medium]

And the idea is, middle order traversal if it’s increasing.

Use a Max as a variable to verify the value, and compare the preceding value with the following value in middle order. If the value increases continuously, the binary search tree is satisfied.

const isValidBST = root => {
    let isValidBSTFlag = true;
    let max = -Number.MAX_VALUE;
    const orderSearch = root => {
        if (root) {
            orderSearch(root.left);
            if (root.val > max) {
                max = root.val;
            } else {
                isValidBSTFlag = false;
            }
            orderSearch(root.right);
        }
    }
    orderSearch(root);
    return isValidBSTFlag;
};
Copy the code

The last non-recursive solution.

The idea of sequential traversal in non-recursion is to use a stack, pushing the left subtree of a node all the way to the leaf node, and then working on the left and root nodes before working on the right subtree.

The loop repeats until the stack is empty.

const isValidBST = root => {
    if(! root)return true;
    let stack = [];
    let isValidBSTFlag = true;
    let max = -Number.MAX_VALUE;
    while (1) {
        while(root ! = null){ stack.push(root); root = root.left; }if (stack.length === 0) break;
        let node = stack.pop();
        if (node.val > max) {
            max = node.val;
        } else {
            isValidBSTFlag = false;
            break;
        }
        root = node.right;
    }
    return isValidBSTFlag;
}
Copy the code

Three, binary search tree insertion

Related Topics:Leetcode 701. Insert operations in binary search trees[medium]

Inserts the value into a binary search tree, as long as the tree remains a binary search tree after insertion.

Find a node greater than the value of the node to be inserted, and use the node to be inserted as the left subtree of that node. Pay attention to detail.

I’m going to use middle order traversal again, and middle order traversal is a nice way of dealing with cases where the value of the node being inserted is larger than all of the nodes in the tree.

In this case, find the largest node in the tree and use the inserted node as the right node of that node.

I don’t have recursion. It’s easy to understand.

const insertIntoBST = (root, val) => {
    let stack = [];
    let r = root;
    let node = null;
    while (1) {
        while(root ! = null) { stack.push(root); root = root.left; }if (stack.length === 0) break; node = stack.pop(); // Find the node greater than the value of the inserted nodeif (node.val > val) {
            letnewNode = new TreeNode(val); newNode.left = node.left; // Here is the detail node.left = newNode;break; } root = node.right; } // The value of the node to be inserted is larger than all the nodes in the treeif (val > node.val) {
        node.right = new TreeNode(val);
    }
    return r;
};
Copy the code

Four, the recovery of binary search tree

Related Topics:Leetcode 99. Restore binary search trees[difficult]

Requirement: Two nodes in a binary search tree were swapped incorrectly. Please restore the tree without changing its structure.

Use middle order traversal to find two nodes s1 and s2 that are in error. Swap these two nodes.

Use an array to store the values of the traversal. If the previous node is greater than the next node, s1 must be the previous node, and the next node may not be S2. Keep traversing and find S2.

const recoverTree = root => {
    let res = [];
    let s1 = s2 = null;
    const orderSearch = root => {
        if (root) {
            orderSearch(root.left);
            if(res.length ! = = 0) {if(res[res.length-1]. Val > root.val) {// select s1 from s1. s1 && (s1 = res[res.length - 1]); S2 = root; s2 = root; } } res.push(root) orderSearch(root.right); } } orderSearch(root); [s1.val, s2.val] = [s2.val, s1.val];return root;
};
Copy the code

Conclusion:

Binary search trees are related to sorting and always operate around middle-order traversal.

Recursive code is concise but hard to understand, while non-recursive code is relatively easy to understand. The efficiency difference between the two is not too big, depending on the scenario used.