Expressions Notations

Infix: a + b
Prefix: + a b
Postfix or reverse polish notation: a b + (Postfix and Prefix are parentheses-free)
postfix( 4 2 3 + * ) = infix( (2 + 3) * 4)
LOG RULES: 1) logb(M *(/) N) = logbM +(-) logbN 2) logbMk = k * logbM 3) logbbk = k
The height of a tree is the length of the longest path from the root to a leaf. It is the number of edges on the longest path from the root
to a leaf. It can also be described as the number of levels in the tree minus one.
The depth of a node n is the length of the path from the root to n.
A Binary search tree(BST) is a binary tree in which the left child of a node is less than the parent node. The right child of a node is
greater than or equal to the parent node.
Full Binary tree is a binary tree where every node has either 0 or 2 children.
Complete Binary Tree is a binary tree in which all levels are fully filled except possibly the last level, which is filled from left to right.
Perfect Binary Tree is a binary tree in which all internal nodes have exactly two children and all leaf nodes are at the same level
The Number of Nodes in a Perfect Tree:
Claim: A perfect tree of height h has a total of 2h+1 - 1 nodes.
The Basis:
For h = 0, the same is 20 = 1 and 20+1 -1 = 1, which satisfies the claim.
The Inductive Step:
The Induction Hypothesis: Assume for an arbitrary integer k >= 0, the formula holds, meaning
∑ki=0 2i = 2k+1 + 1.
The Inductive Claim: We need to prove that the property is true for k+1 i.e. ∑k+1i=0 2i = 2k+2 - 1.
Proof:
∑k+1i=0 2i = (∑ki=0 2i)+ 2k+1
= (2k+1 - 1) + 2k+1 (by inductive hypothesis)
= 2*2k+1 - 1
= 2k+2 - 1
Hence, by mathematical induction, the claim is proved.
Proving the Height of a Perfect Tree is O(log n):
Claim: the height h of a perfect binary tree with n nodes is O(log n).
Proof:
1) A perfect binary tree of height h has 2h+1 - 1 nodes. Meaning The tree has twice as many nodes as the level
above it.
2) Let n be the number of nodes in the tree. We can write n = 2h+1 - 1. By rearranging the equation, we get n + 1 =
2h+1.
3) Taking the log2 of both sides, we get log2(n+1) = h+1*log2(2). Therefore, h = log2(n+1) - 1. Since log2(n+1) is
O(log n), the height of the tree is O(log n).
Predecessor: The largest node that is smaller than a given node. Typically, it is the rightmost node in the left subtree.
Successor: The smallest node that is greater than a given node. Typically, it is the leftmost node in the right subtree.
Recursive Traversal Methods
Inorder: left, root, right
Preorder: root, left, right
Postorder: left, right, root
Level Order: level by level from left to right
Search Methods
Depth First Search (DFS): Inorder, Preorder, Postorder
Breadth First Search (BFS): Level Order
Inorder Traversal: Traverse the tree in an inorder manner: left subtree first, then the root, and finally the right subtree.
Preorder Traversal: Traverse the tree in a preorder manner: root first, then the left subtree, and finally the right subtree.
Inorder: Algorithm: Code: Preorder: Algorithm Code
Traverse the left subtree. void inorder(node) Visit the root. void preorder(node)
Visit the root. if node is null: return Traverse the left subtree. if node is null: return
Traverse the right subtree. inorder(node.left) Traverse the right subtree. visit(node)
visit(node) preorder(node.left)
inorder(node.right) preorder(node.right)
Proving that f(n) is O(n2) with Limit Test
To verify that f(n) = 4n2 + n + 20 is O(n2), we can use the limit test with L’Hospital’s rule. We are trying to examine the limit of the
ratio of f(n) to n2 as n approaches infinity:
limn->oo (4n2 + n + 20) / n2
= limn->oo 4 + 1/n + 20/n2 (As n approaches infinity, 1/n and 20/n2 approach 0.)
= limn->oo 4 = 4
Since the limit is a constant, f(n) is O(n2) by the limit test for Big O notation. <- this one is correct
Since the limit is a 0, f(n) is not O(n2) since f(n) grows at a rate slower or equal to g(n) = n2 as n increases.
Proving that f(n) is O(log n) with Limit Test
To verify that f(n) = 3log(n) + log(log(n)) is O(log(n)), we can use the limit test with L’Hospital’s rule. We are trying to examine the
limit of the ratio of f(n) to log(n) as n approaches infinity:
limn->oo ( 3log(n) + log(log(n)) ) / log(n)
= limn->oo 3 + log(log(n)) / log(n)
= limn->oo 3 + 1 / n log(n) / 1 / n
= limn->oo 3 + 1 / log(n) (1/log(n) approaches 0)
Since the limit is a constant, f(n) is O(log n) by the limit test for Big O notation.
Time complexity O(n!)
void permite(array, start, end):
if start == end: print(array)
else:
for i from start to end: <- with each recursion m becomes smaller -1
swap(array[start], array[i]) <- ignore O(1)
permite(array, start+1, end) <- iterates by 1
swap(array[start], array[i]) <- ignore O(1)
O(n) x O(n-1) x … x O(0) (if we flip it it will be factorial pattern)
Big OH notations O(1) >= O(log n) >= O(n) >= O(n2) >= O(nk) >= O(an)
O(a x g) = O(g) Θ(Theta) is a exact value of n (not worse nor better)
O(f) +(*) O(g) = O(f +(*) g) O(Oh) is a upper a proximate value of n (not worse)
O(O(g)) = O(g) Ω(Omega) is a lower a proximate value of n (not better)
O(sum of terms) = O(highest degree)
nm = O(an)
log nm = O(log n)
logm n = O(nk)
The Bound function is a way to prove termination of a algorithm for A(p)
Proof:
1. f(0) <= 0, for the base case of p
2. f(p) > 0, for the recursive case
3. For any recursive call A(q) with q < p, f(q) < f(p)
Therefore, A(p), n >= 0 terminates
⁠In a binary tree, if a node has one child only, it must be designated as either left or right because the tree is *ordered*.
A binary tree is considered *full* if every node has exactly two children or no children.
A *perfect* binary tree is full and all its leaves are at the same level,meaning it’s completely symmetrical.
⁠The depth of a node is the length of the path from the *root* to the node itself.
In inorder traversal, one starts at the *leftmost* node and follows the pattern up the tree, which results in elements processed in *ascending* order for
a binary search tree.
⁠During preorder traversal, one begins at the root and then *explores* the left side of the tree, visiting the nodes all the way down before moving to the
right subtree.
⁠Postorder traversal ensures that all nodes in the left and right subtrees are visited before the *root* node.
A complete binary tree is filled at all levels except possibly the last level, which is filled from *left* up to a certain point.
The height of a node n is defined as the longest path from n to a *leaf*.
⁠In a *complete* binary tree, every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
The *height* of a tree is the number of edges from the root to the furthest leaf.
The *inorder* traversal process involves visiting the left subtree, the node itself, and then the right subtree.
*Preorder* traversal starts at the root and explores as far as possible along each branch before backtracking.
*Postorder* traversal in a binary tree means to visit all the nodes on the left before visiting the node itself and then proceeding to the right subtree.
⁠The *level* of any node is the level of its parent plus one.
To find the *predecessor* of a node in a binary search tree, one would look for the rightmost node in the left subtree. (largest nod)
⁠To find the *successor* of node in a binary scratch tree, one would look for leftmost node in the right subtree.(smallest nod)