Basics

基本性质

• 左子树都 < root, 右子树都 > root, =的情况 非BST
• 中序遍历一定是有序的 (ascending order)
  • 如果一棵二叉树的中序遍历不是升序，则一定不是BST
  • 如果一棵二叉树的中序遍历是升序，也未必是BST
    • 当存在重复元素时，相同的数要么同时在左子树，要么同时在右子树，不能一边一个

基本操作

• insert node in BST
• delete node in BST
• o(height) 的时间search, insert, delete

Problems

Validate BST: http://www.lintcode.com/en/problem/validate-binary-search-tree/

• traverse vs divide & conquer

BST iterator: http://www.lintcode.com/en/problem/binary-search-tree-iterator/

• iterator vs inorder with non-recursion

In-order Successor in BST: http://www.lintcode.com/problem/inorder-successor-in-binary-search-tree/

Search Range in BST: http://www.lintcode.com/problem/search-range-in-binary-search-tree/

Insert Node in a Binary Search Tree: http://www.lintcode.com/problem/insert-node-in-a-binary-search-tree/

Remove Node in a Binary Search Tree: http://www.lintcode.com/problem/remove-node-in-binary-search-tree/

• http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/BST-delete.html

Binary Tree Zigzag Level Order Traversal: http://www.lintcode.com/en/problem/binary-tree-zigzag-level-order-traversal/

Binary Tree Level Order Traversal II: http://www.lintcode.com/en/problem/binary-tree-level-order-traversal-ii/