binary trees

binary tree

graph where nodes are restricted to having at max 2 children (L and R).
a binary tree is complete when

types of binary trees:

• full: every node has 0 or 2 children
• perfect: all interior nodes have 2 childre
• complete: every lvl except possibly the last is completely filled and all the nodes on the last lvl are as far left as possible.
• balanced: binary tree structure in which the left and right subtrees of every node differ in height (the number of edges from the top-most node to the farthest node in a subtree) by no more than 1 (or the skew is no greater than 1).

Heap

complete binary tree where the children are smaller than the parent.
Heaps are usually used to implement priority queues, where the smallest (or largest) element is always at the root of the tree.

used for heap sort.

• min heap: children a less than or equal to parent.
• max heap: children are greater than or equal value to parent.

useful for finding the min or max value in a collection.

getting min/max value is O(logn)

binary search tree

binary tree where the left children is <= than parent and right child is >=
used for searching algorithms, or rather checking whether a val exists in the structure.

time complexity is O(logn) for search, insertion, and deletion.

balanced binary tree

tree where the difference of height of the left subtree and the right subtree is no more than 1.

perfect binary tree

all interior nodes have two children and all leaves have the same level. ex: ancestry chart of a person

complete binary tree (or almost complete)

all interiors nodes have two children except maybe on the last level, where nodes get added from left to right.
sometimes referred as almost complete.

full binary tree

binary tree where each node has two children or no children at all