Tree, Heap and Trie

A tree normally refers to a binary tree. Each node contains a left node and right node like the following:

class TreeNode{ int value; TreeNode left; TreeNode right; }

Here are some concepts related with trees:

1. Binary Search Tree: for all nodes, left children <= current node <= right children
2. Balanced vs. Unbalanced: In a balanced tree, the depth of the left and right subtrees of every node differ by 1 or less.
3. Full Binary Tree: every node other than the leaves has two children.
4. Perfect Binary Tree: a full binary tree in which all leaves are at the same depth or same level, and in which every parent has two children.
5. Complete Binary Tree: a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible

Heap is a specialized tree-based data structure that satisfies the heap property. The time complexity of its operations are important (e.g., find-min, delete-min, insert, etc). In Java,PriorityQueue is important to know.

4.1 Tree

1) Binary Tree Traversal: Preorder, Inorder, Postorder, Level Order, Level Order II, Vertical Order
2) Invert Binary Tree
3) Kth Smallest Element in a BST
4) Binary Tree Longest Consecutive Sequence
5) Validate Binary Search Tree
6) Flatten Binary Tree to Linked List
7) Path Sum (DFS or BFS)
7) Path Sum II (DFS) 
8) Construct Binary Tree from Inorder and Postorder Traversal
8) Construct Binary Tree from Preorder and Inorder Traversal
9) Convert Sorted Array to Binary Search Tree [Google]
10) Convert Sorted List to Binary Search Tree [Google]
11) Minimum Depth of Binary Tree
12) Binary Tree Maximum Path Sum *
13) Balanced Binary Tree
14) Symmetric Tree
15) Binary Search Tree Iterator 
16) Binary Tree Right Side View
17) Lowest Common Ancestor of a Binary Search Tree
18) Lowest Common Ancestor of a Binary Tree
19) Verify Preorder Serialization of a Binary Tree
20) Populating Next Right Pointers in Each Node 
21) Populating Next Right Pointers in Each Node II 
21) Unique Binary Search Trees (DP)
21) Unique Binary Search Trees II (DFS)
22) Sum Root to Leaf Numbers (DFS)
23) Count Complete Tree Nodes 
24) Closest Binary Search Tree Value
25) Binary Tree Paths
26) Maximum Depth of Binary Tree
27 Recover Binary Search Tree
28) Same Tree
29) Serialize and Deserialize Binary Tree
30) Inorder Successor in BST

4.2 Heap

1) Merge k sorted arrays [Google]
2) Merge k Sorted Lists *
3) Find Median from Data Stream
4) Meeting Rooms II

4.3 Trie

1) Implement Trie (Prefix Tree)
2) Add and Search Word - Data structure design (DFS)

4.4 Segment Tree

1) Range Sum Query - Mutable
2) The Skyline Problem