Tree
Binary Search Tree
Fact1. Inorder traversal of BST
Fact2. Successor (after node)
Fact3. Predecessor (before node)
![](images/succ2.png)
(The above image is from leetcode.com.)
[Medium] No.701 Insert into a Binary Search Tree
Approach: recursion
Time Complexity: O(H), H = logN if it's a balanced tree. O(H)/O(logN) in the average case, and O(N) in the worst case.
Space Complexity: O(H) to keep the recursion stack, where H is a tree height. H =logN for the balanced tree. O(N) in the worst case.
[Medium] No.450 Delete Node in a BST
Approach: recursion and finding successor
Time Complexity: O(H), H = logN if it's a balanced tree. O(H)/O(logN) in the average case, and O(N) in the worst case.
Space Complexity: O(H) to keep the recursion stack, where H is a tree height. H =logN for the balanced tree.
[Medium] No.96. Unique Binary Search Trees
![](images/96_BST.png)
(The above image is from leetcode.com.)
Approach: dynamic programming
Time Complexity: O(N^2)
Space Complexity: O(N)