Tree

Traversal

• Inorder
  • left → node → right
• Preorder
  • node → left → right
• Postorder
  • left → right → node

Binary Tree

• Tree with nodes that only has two children

Binary Search Tree (BST)

• Left child of a node must be smaller
• Right child of a node must be larger
• O(log(n)) searching

Self-Balancing Binary Search Tree (AVL Tree)

• Balance B(n) = H(l) - H(r)
  • B(n) <= abs(threshold)
• Left, right, left-right, right-left rotation

Prefix Tree (Trie)

• Efficient pattern matching
• Maintain a isWord variable and an array for a node’s children

Interval Tree