Trees:
A tree is a nonlinear hierarchical data structure that consists of nodes connected by edges.
Root → The topmost node of the hierarchy is called the root of the tree.
Child → Nodes next in the hierarchy are the children of the previous node.
Parent → The node just previous to the current node is the parent of the current node.
Siblings → Nodes with the same parent are called siblings.
Tree Traversals:
In order to perform any operation on a tree, you need to reach to the specific node. The tree traversal algorithm helps in visiting a required node in the tree. There are 4 major types of traversals
– Pre-order Traversal (Node, Left Subtree, Right Subtree)
– In-order Traversal (Left Subtree, Node, Right Subtree)
– Post-order Traversal (Left Subtree, Right Subtree, Node)
– Level-order Traversal
Graphs:
A graph data structure is a collection of nodes that have data and are connected to other nodes.
There are two main traversals in graphs
– DFS
– BFS
DFS:
The DFS algorithm is a recursive algorithm that uses the idea of backtracking. It involves exhaustive searches of all the nodes by going ahead, if possible, else by backtracking.
Here, the word backtrack means that when you are moving forward and there are no more nodes along the current path, you move backwards on the same path to find nodes to traverse. All the nodes will be visited on the current path till all the unvisited nodes have been traversed after which the next path will be selected.
BFS:
The BFS algorithm is a traversing algorithm where you should start traversing from a selected node (source or starting node) and traverse the graph layerwise thus exploring the neighbour nodes (nodes which are directly connected to source node). You must then move towards the next-level neighbour nodes.
Disjoint-set:
A data structure representing a dynamic collection of (non-overlapping)sets..
Union-Find:
An algorithm that performs two useful operations on a disjoint-set.
Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset. Union: Join two subsets into a single subset.