__Binary Search Tree__

- A tree is a connected, acyclic, unidirectional graph.
- It emulates a tree structure with a set of linked nodes.
- The topmost node in a tree is called the root node, node of a tree that has child nodes is called an

internal node or inner node and the bottom most nodes are called a leaf node.

- The root is a node that has no parent; it can have only child nodes. Leaves, on the other hand, have

no children.

- The simplest form of a tree is a Binary Tree which has a root node and two subtrees (which is a

portion of a tree data structure that can be viewed as a complete tree in itself) - left and right.

- A Binary Search Tree is a binary tree in which if a node has value N, all values in its left sub-tree

are less than N, and all values in its right sub-tree are greater than N.

- This property called binary search tree property holds for each and every node in the tree.

** Basic operations of Binary Search tree are:**

- Finding a node with a specific data value.
- Finding a node with minimum or maximum data value.
- Insertion and deletion of a node.
- Three (preorder, postorder and inorder) operations for depth-first traversal of a tree

- Visit a node before traversing it’s sub-trees

- Visit a node after traversing it’s left subtree but before traversing it’s right sub-tree

- Visit a node after traversing all of it’s subtrees
- Binary search tree has three properties: data stands for the value of the node, *left is the left subtree

of a node and *right (a pointer of type struct treeNode) is the right subtree of a node.

__Heap__

- The Heap data structure is an array object that can be viewed as a complete and balanced

binary tree.

- Min (Max)-Heap has a property that for every node other than the root, the value of the node is at

least (at most) the value of its parent.

- Thus, the smallest (largest) element in a heap is stored at the root, and the sub-trees rooted at a

node contain larger (smaller) values than does the node itself.

- A Min-heap viewed as a binary tree and an array.
- Heaps can be used as an array.
- For any element at array position I, left child is at ( 2i ), right child is at ( 2i+1 ) and parent is at

(int) (i / 2).

- Heap size is stored at index 0.
- Basic operations of a heap are:

- Insert – Insert an element.
- Delete minimum – Delete and return the smallest item in the heap.

- Worst case complexity of Insert is O (lg n), where n is the number of elements in the heap.
- Worst case running time of DeleteMin is O (lg n) where n is the number of elements in the heap.

**Graphs and Graph Algorithms **

### Depth-First Search

- Depth-first search algorithm searches deeper in graph whenever possible.
- In this, edges are explored out of the most recently visited vertex that still has unexplored edges

leaving it.

- When all the vertices of that vertex’s edges have been explored, the search goes backtracks to

explore edges leaving the vertex from which a vertex was recently discovered.

- This process continues until we have discovered all the vertices that are reachable from the

original source vertex.

- It works on both directed and undirected graphs.

**Analysis**

- The DFS function is called exactly once for every vertex that is reachable from the start vertex.
- Each call looks at the successors of the current vertex, so total time is O(# reachable nodes + total

# of outgoing edges from those nodes).

- The running time of DFS is therefore O(V + E).

### Breadth-First Search

- Breadth-first search is one of the simplest algorithms for searching a graph.
- Given a graph and a distinguished source vertex, breadth-first search explores the edges of the

graph to find every vertex reachable from source.

- It computes the distance (fewest number of edges) from source to all reachable vertices and

produces a “breadth-first tree” with source vertex as root, which contains all such reachable

vertices.

- It works on both directed and undirected graphs.
- This algorithm uses a first-in, first-out Queue Q to manage the vertices.

**Analysis **

- Initializing takes O(V) time The queue operations take time of O(V) as enqueuing and

dequeuing takes O(1) time.

- In scanning the adjacency list at most O(E) time is spent.
- Thus, the total running time of BFS is O(V + E).

### Dijkstra’s Algorithm

- Dijkstra’s algorithm solves the single source shortest path problem on a weighted, directed

graph only when all edge-weights are non-negative.

- It maintains a set S of vertices whose final shortest path from the source has already been

determined and it repeatedly selects the left vertices with the minimum shortest-path estimate,

inserts them into S, and relaxes all edges leaving that edge.

- In this we maintain a priority-Queue which is implemented via heap.

** Algorithm (described in detail within the document for this tutorial)**

- Input Format: Graph is directed and weighted.
- First two integers must be number of vertices and edges which must be followed by pairs of

vertices which has an edge between them.

### Floyd-Warshall Algorithm

- Floyd-Warshall algorithm is a dynamic programming formulation, to solve the all-pairs

shortest path problem on directed graphs.

- It finds shortest path between all nodes in a graph.
- If finds only the lengths not the path.
- The algorithm considers the intermediate vertices of a simple path are any vertex present in that

path other than the first and last vertex of that path.

- Input Format: Graph is directed and weighted.
- First two integers must be number of vertices and edges which must be followed by pairs of

vertices which has an edge between them.

### Bellman –Ford

- The bellman-Ford algorithm solves the single source shortest path problems even in the cases

in which edge weights are negative.

- This algorithm returns a Boolean value indicating whether or not there is a negative weight cycle

that is reachable from the source.

- If there is such a cycle, the algorithm indicates that no solution exists and it there is no such cycle,

it produces the shortest path and their weights.

- The Bellman-Ford algorithm runs in time O(VE), since the initialization takes Θ(V) time, each

of the |V| - 1 passes over the edges takes O(E) time and calculating the distance takes O(E) times.