Tree

• Complete binary tree:
  Definition of a complete binary tree from Wikipedia:
  In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes inclusive at the last level h.

• Specific ordering property:
  all left descendants <= n < all right descendants. Must be true for all node n.
  Make sure to check whether if there’s any duplicate value. One definition is no duplication, the other is duplication will be on right or either side.

• Complete Binary Tree:
  Every level is filled except for perhaps last level. To the extent that the last level is filled, it is filled left to right.
  

• Full Binary Tree
  A full binary tree is every node has either zero or two children. That is, no nodes have only one children.

• Perfect Binary Tree
  Both full and complete. All leaf nodes are on same level, and this level have maximum nodes. Have exactly 2^h -1 nodes, h is number of levels(height).

• Trie(Prefix Trees)
  Each path down the tree would represent a word. Normally, have a * node(sometimes called null node)

Questions to ask for clarify

What type of tree?

• binary tree, binary search tree.
• balanced or unbalanced tree.
  balanced means it ensures $O(logn)$ time to insert and find.
• full binary tree: each node have two or zero children.
• complete binary tree: only right bottom part is missing.

empty tree
duplicate node. If it’s a BST, does duplicate node goes left or right?
skewed tree