Every computable function can be computed using Lists as the only data structure!
IntList cons(int newElement, IntList oldList)
Precondition: None.
Postconditions: If x = cons(newElement, oldList) then 1. x refers to a newly created object; 2. x != nil; 3. first(x) = newElement; 4. rest(x) = oldList
2. The remaining nodes are divided into two disjoint subsets, L and R, each of which is a binary tree. L is called the left subtree of T and R is called the right subtree of T.
There are at most 2d nodes at depth d of a binary tree.
A binary tree with n nodes has height at least Ceiling[lg(n+1)] – 1.
A binary tree with height h has at most 2h+1 –1 nodes
Stacks
A stack is a linear structure in which insertions and deletions are always make at one end, called the top.