Trees

When thinking about trees, think recursion. Trees are a type of graph where child nodes consist of their own subtrees. Trees have a root node at the top. The edges of a tree are typically directional towards a node's children, and are acyclic. Each child node can only have one parent. The space complexity of trees are O(n) because you have n nodes and constant edges based on n.

Binary Tree

Each node in a binary tree has at most 2 children. Many operations on a binary tree have logarithmic time complexity. K-ary trees is a way of describing trees where nodes have at most k children.

Types of Binary Trees

Perfect Binary Trees are where all the interior nodes have two children, and the leaf (bottom) nodes have the same depth.

Complete Binary Trees are where all interior nodes have two children, but the leaf nodes aren't all at the same depth. Essentially, the bottom level is not fully filled, however it must be filled from left to right.

Balanced Binary Trees are where all left and right subtrees depth differs by no more than 1. This is what allows trees to have a O(log(n)) search complexity.

Full Binary Trees are where all child nodes have either zero or two child nodes. No child nodes have only one child.

Binary Search Tree

A binary search tree or BST is a tree where the left child node is always less than the parent, and the right child node is always greater. This allows for very fast searching since it is easy to make a decision on which path to check down next.