Cracking the Coding Interview Ch 4. Trees and Graphs Summary (pp.100-105)
December 13, 2022
4. Trees and Graphs
- Tree: a data structure composed of nodes (any data type as values), which may or may not be in a particular order.
- Types of trees
- Binary tree: a tree in which each node has up to two children
- Binary search tree: a binary tree in which every node fits a specific ordering property: all left descendants <= n < all right descendants
- Types of binary trees
- Complete binary tree: a binary tree in which every level of the tree is fully filled, except for perhaps the last level
- Full binary tree: a binary tree in which every node has either zero or two children (no nodes have only one child).
- Perfect binary tree: a tree where all interior nodes have two children and all leaf nodes are at the same level
- Binary tree traversal
- In-order traversal: “visit” the left branch -> current node -> the right branch
- Pre-order traversal: “visit” the current node -> child nodes
- Post-order traversal: child nodes -> “visit” the current node
- Binary heaps (min-heaps and max-heaps)
- Min-heap: a complete binary tree where each node is smaller than its children.
- Insert: by inserting the element at the bottom and moving it up to the right place
- Extract minimum element: remove the minimal element and swap it with the last element in the heap and then move it down to the right place
- Tries (Prefix Trees)
- Trie (a prefix tree): a variant of an n-ary tree in which characters are stored at each node
- * nodes: a special type of child to mark the end of word
- O(K) time, where K is the length of the string