Theory

Concepts

Here is a compilation of concepts learnt so far!

Binary Search

Basics

• Binary Search is an optimised search algorithm.
• It is only valid in sorted algorithms.
• The time complexity is: O(logn)

How it works,

• First we have two pointers, left and right.
• Left points towards the beginning of the array and right points to the end.
• We calculate the median of the array.
• IF: the target is less than the middle element, we search the left half.
• ELSE: we search the right half. Repeat this until we've found the element!

Trees

Basics

• Trees is a non-linear data structure
• Binary Tree: A tree where every node has atmost 2 children
• Types of Binary Trees ** Full Binary Tree: It either has 2 children, or no children. ** Complete Binary Tree/Binary Heaps: The tree is uniformly filled (can be missed out on places, but they are uniformly filled). ** Perfect Binary Tree: All the parents in this tree have exactly 2 children nodes. All leaves are on the same level!

Perfect Binary Tree = Full + Complete

Traversals in tree

• PreOrder : Node, Left, Right
• InOrder: Left, Node, Right
• PostOrder: Left, Right, Node

Traversals

• Depth First Search: This search starts from a node till its leaf (Uses Recursion/Stack)
• Breadth First Search: This search analyses all the nodes on a level (Uses a Queue)