BST

// Definition for a binary tree node.
 struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

BST is an important data structure. Many frequently asked interview questions are related to BST.

Official definition of BST is all left subtree is smaller than Node, and all right subtree is larger than Node. This means there is no duplicate in BST.

Corresponds to map in C++.

If there are duplicates in BST. Then the definition change to all left subtree is not larger than Node and all right subtree is not smaller than Node.

Corresponds to multimap in C++.

m_map.insert(std::pair<int, int>(key, val))
The relative ordering of elements with equivalent keys is preserved, and newly inserted elements follow those with equivalent keys already in the container.

Functions

interator
begin() gives the smallest item
rbegin() gives the largest

lower_bound(v.begin(), v.end(), 20) return iterator to iterm not less than 20

upper_bound(v.begin(), v.end(), 20) return iterator to iterm greater than 20