Binary Search Tree is one of the commonly used binary tree. Its definition is that all nodes on the left subtree are <= the node, and all nodes on the right subtree are >= the node.

BST’s value has orders. Therefore, most of its operations doesn’t need to search both right and left subtree, and its template is a bit different from the general traverse.

The blog is written based on labuladong git book.

void BST(TreeNode root, int target) {
    if (root.val == target)
        // 找到目标，做点什么
    if (root.val < target) 
        BST(root.right, target);
    if (root.val > target)
        BST(root.left, target);
}

Also, BST’s in-order traverse is sorted. It is commonly used with in-order traversal.

Problems

95. Validate Binary Search Tree

1524. Search in a Binary Search Tree

11. Search Range in Binary Search Tree

85. Insert Node in a Binary Search Tree

(Leetcode) 1008. Construct Binary Search Tree from Preorder Traversal

87. Remove Node in Binary Search Tree

106. Convert Sorted List to Binary Search Tree

448. Inorder Successor in BST

(Leetcode) 897. Increasing Order Search Tree