#Algorithms Part 1: Graphs, BFS,DFS, Dijkstra Algorithm, Bellman-Ford Algorithm

ALSO CHECK: Algorithms

Graph Traversal

• Its the process of visiting and exploring a graph for processing.
• In this we visit and explore each vertex and edge in a graph such that all the vertices's are explored exactly once.
• Visiting a node means selecting a node, where as exploring means exploring the children nodes of the node which we have visited.

Breadth First Search

• Its an algorithm for traversing trees and graphs.
• In BFS we start with the root node, explores all sibling nodes before moving on to the next level of siblings.
• Queue is the main data structure which is used while performing BFS.
• BFS is used as a crawlers in web-engines. It is the main algorithm which is used for indexing the web pages, it starts from the source page and follows all the links associated with that page. In this case each link is considered as a node in the graph.
• BFS is also used in GPS navigation to find the neighboring locations.
• BFS is also used in finding the shortest path

Binary Search Trees, Balance Search Trees, 2-3 ST, Red- Black BST

ALSO CHECK: Algorithms and System Design Interview Questions

Tree Data Structure

• If we compare sorted arrays with linked list: Search is fast in SA (O(logn)) and slow in LL (O(n)), but insert & delete is slow in SA (O(n)) and fast in LL (O(1)).
• Binary search trees are very balanced in the sense that all these common operations like insert, delete, and search take about the same time (log n).
• In Binary search trees we have the nodes, which contain the data. Nodes are connected to other nodes through edges. The top node of the tree is called the root node (in a tree data structure, there can only be one root node).
• A node which has no children is called a leaf node. 
• Any node may be considered to be the root of a subtree, which consists of its children and its children's children and so on. The level of a node tells us how far it is from the root. 

How to check if a Tree is subtree of another Tree?

ALSO CHECK: Algorithms and System Design Interview Questions

To check if the given tree is subtree of another tree, first we need to undertand if the how can we check if the tree's are identical or not.

Please visit: Check if two Binary Trees are Identical or not?

To verify if a tree is subtree of another, we need to traverse the Tree T in a preorder fashion.For every visited node in the traversal, see if the subtree rooted with this node is identical to another tree S.

How to check of two Binary Trees are Identical?

ALSO CHECK: Algorithms and System Design Interview Questions

Two Binary trees are identical when they have same data and structure/arrangement of data is also same. To find if they are identical or not, we need to traverse both the trees simultaneously, and in each iteration we will compare the data of current node and the children of both the trees.

Bottom View of a Binary Tree

ALSO CHECK: Algorithms and System Design Interview Questions

Recently I had given interview in Morgan Stanley for Senior Java Developer profile, the intervier asked me, we have a balanced Binary Tree, am trying to throw a light from a particular node, which all nodes will be visible?

I tried my best, but failed to write an algorithm. After the interview I realized he was asking to write an algorithm to see the bottom view of a Binary Tree.

The bottom view of a binary tree refers to the bottommost nodes present at their horizontal distance.

If we see the tree from bottom from a particular node, which all nodes will be visible is the bottom view of a Binary Tree.

The bottom view of above Binary Tree is: 7, 5, 8, 6

Vertical Order Traversal of a Binary Tree

ALSO CHECK: Algorithms and System Design Interview Questions

Let's say we have below Binary Tree

In vertical traversal, we print nodes of a binary tree in vertical order by assuming that the left and right child of a node makes 45 degree angle with the parent.

We need to check the Horizontal Distances from the root for all nodes. If two nodes have the same Horizontal Distance (HD), then they are on the same vertical line.

Level Order Traversal of a Binary Tree

ALSO CHECK: Algorithms and System Design Interview Questions

Let's say we have below Binary Tree

We need to print nodes level by level. i.e. all nodes present at level 1 should be printed first followed by nodes of level 2 and so on. All nodes for any level should be printed from left to right.