Self-balanced BST => O(log n) complexity

Either:

- 2-node: contains a single value and has two children
- 3-node: contains two values and has three children
- Leaf: 1 or 2 keys

Insert: find proper leaf and insert the value in-place. If the leaf has 3 values (called temporary 4-node), split the node into three 2-node and insert the middle value into the parent.

If tree is not balanced, rearange the nodes with single or double rotations

All: O(log n)

Self-balanced BST => O(log n) complexity

Can have more than two children (generalization of 2-3 tree)

Use-case: huge amount of data that cannot fit in main memory but disk space.

Height is kept low to reduce the disk accesses.

Match how page disk are working

The balance factor of each node (the difference between the two subtree heights) should never exceed 1

Guarantee of O(log n) search

- B-tree: paging from disk (database)
- Red-black tree: fairly frequents inserts, deletes or retrievals
- AVL tree: many retrievals, infrequent inserts and deletes

BFS: time O(v), space O(v)

DFS: time O(v), space O(h) (height of the tree)

Level order traversal (level by level)

Iterative algorithm: use a queue, put the root, iterate while queue is not empty

```
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()) {
Node node = queue.poll();
visit(node);
if(node.left != null) {
queue.add(node.left);
}
if(node.right != null) {
queue.add(node.right);
}
}
```

Tree with each node having up to two children

- In-order: left-root-right
- Pre-order: root-left-right
- Post-order: left-right-root

Itβs depth first so:

- In-order: 1, 2, 3, 4, 5, 6, 7
- Pre-order: 3, 2, 1, 5, 4, 6, 7
- Post-order: 1, 2, 4, 7, 6, 5, 3

Every level of the tree is fully filled, with last level filled from the left to the right

Each node has 0 or 2 children

2^l - 1 nodes with l the level: 1, 3, 7, etc. nodes

Every level is fully filled

If not balanced O(n)

If balanced O(log n)

Binary tree in which every node must fit the property: all left descendents <= n < all right descendents

Implementation: optional key, value, left, right

Find inorder successor and swap it

Average: O(log n)

Worst: O(h) if not self-balanced BST, otherwise O(log n)

Search for key or value (by recursively going left or right depending on the comparison) then insert a new node or reset the value (no swap)

Complexity: worst O(n)

```
public TreeNode insert(TreeNode root, int a) {
if (root == null) {
return new TreeNode(a);
}
if (root.val <= a) { // Left
root.left = insert(root.left, a);
} else { // Right
root.right = insert(root.right, a);
}
return root;
}
```

Is it a self-balanced BST? (impacts: O(log n) time complexity guarantee)

Time and space: O(n * l) with n the number of words and l the longest word length

Time: O(k) with k the size of the key

Space: O(1) iterative, O(k) recursive

Time: O(k) with k the size of the key

Space: O(1) iterative or O(k) recursive

Solution: BFS by popping only a fixed number of elements (queue.size)

```
public static List<List<Integer>> traverse(TreeNode root) {
List<List<Integer>> result = new LinkedList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<>();
int levelSize = queue.size();
// Pop only levelSize elements
for (int i = 0; i < levelSize; i++) {
TreeNode current = queue.poll();
level.add(current.val);
if (current.left != null) {
queue.add(current.left);
}
if (current.right != null) {
queue.add(current.right);
}
}
result.add(level);
}
return result;
}
```

Example: 1 -> 7 -> 3 gives 173

Solution: sum = sum * 10 + n

```
private int dfs(TreeNode node, int sum) {
if (node == null) {
return 0;
}
sum = 10 * sum + node.val;
// Do something
}
```

Move recursively on the left (on the right)

Self-balanced BST => O(log n) complexity

- Root node always black
- Incoming node is red
- Red violation: child and parent are red
- Resolve violation by recoloring and/or restructuring

Binary Trees: Red Black by David Pynes

All: O(log n)

```
public void reverse(Node node) {
if (node == null) {
return;
}
Node temp = node.right;
node.right = node.left;
node.left = temp;
reverse(node.left);
reverse(node.right);
}
```

Tree-like data structure with empty root and where each node store characters

Each path down the tree represent a word (until a null node that represents the end of the word)

Usually implemented using a map of children (or a fixed size array with ASCII charset for example)

Use case: dictionnary (save memory)

Also known as prefix tree

Sorted keys