Tree
A tree data structure is a non-linear data structure because it does not store in a sequential
manner. It is a hierarchical structure as elements in a Tree are arranged in multiple levels.
In the above structure, each node is labeled with some number. Each arrow shown in the above
figure is known as a link between the two nodes.
Root: The root node is the topmost node in the tree hierarchy. In other words, the root
node is the one that doesn't have any parent. In the above structure, node numbered 1 is
the root node of the tree. If a node is directly linked to some other node, it would be
called a parent-child relationship.
Child node: If the node is a descendant of any node, then the node is known as a child
node.
Parent: If the node contains any sub-node, then that node is said to be the parent of that
sub-node.
Sibling: The nodes that have the same parent are known as siblings.
Leaf Node:- The node of the tree, which doesn't have any child node, is called a leaf
node. A leaf node is the bottom-most node of the tree. There can be any number of leaf
nodes present in a general tree. Leaf nodes can also be called external nodes.
Internal nodes: A node has atleast one child node known as an internal
Ancestor node:- An ancestor of a node is any predecessor node on a path from the root to
that node. The root node doesn't have any ancestors. In the tree shown in the above
image, nodes 1, 2, and 5 are the ancestors of node 10.
Descendant: The immediate successor of the given node is known as a descendant of a
node. In the above figure, 10 is the descendant of node 5.
Binary Tree
The Binary tree means that the node can have maximum two children. Here, binary name itself
suggests that 'two'; therefore, each node can have either 0, 1 or 2 children.
Binary Search tree
A binary search tree follows some order to arrange the elements.
In a Binary search tree,
The value of left node must be smaller than the parent node, and
The value of right node must be greater than the parent node.
This rule is applied recursively to the left and right sub trees of the root.
Example of creating a binary search tree
Suppose the data elements are - 45, 15, 79, 90, 10, 55, 12, 20, 50.
Tree Traversal
Traversal is a process to visit all the nodes of a tree and may print their values too. Because,
all nodes are connected via edges (links) we always start from the root (head) node. That is,
we cannot randomly access a node in a tree. There are three ways which we use to traverse a
tree −
In-order Traversal (left, root, right)
Pre-order Traversal (root, left, right)
Post-order Traversal (left, right, root)
In-order:
Pre-order:
Post-order:
Example of Tree Traversal:
Minimum Spanning Tree (MST)
A spanning tree is a subset of an undirected Graph that has all the vertices connected by
minimum number of edges.
If all the vertices are connected in a graph, then there exists at least one spanning tree. In a graph,
there may exist more than one spanning tree.
Minimum Spanning Tree
A Minimum Spanning Tree (MST) is a subset of edges of a connected weighted undirected
graph that connects all the vertices together with the minimum possible total edge weight.
To derive an MST, Prim’s algorithm or Kruskal’s algorithm can be used.
Prim's Algorithm
Prim's Algorithm is a greedy algorithm that is used to find the minimum spanning tree from a
graph. Prim's algorithm finds the subset of edges that includes every vertex of the graph such that
the sum of the weights of the edges can be minimized.
Prim's algorithm starts with the single node and explores all the adjacent nodes with all the
connecting edges at every step. The edges with the minimal weights causing no cycles in the
graph got selected.
How does the prim's algorithm work?
The steps to implement the prim's algorithm are given as follows -
First, we have to initialize an MST with the randomly chosen vertex.
Now, we have to find all the edges that connect the tree in the above step with the new
vertices. From the edges found, select the minimum edge and add it to the tree.
Repeat step 2 until the minimum spanning tree is formed.
Now start with the following graph using Prim’s algorithm:
Solution:
Step 1:
Step 2:
Step 3:
Step 4:
Step 5:
Finally, Cost of MST = 4 + 2 + 1 + 3 = 10 units.
Try to solve it:
Kruskal's Algorithm
Kruskal's Algorithm is used to find the minimum spanning tree for a connected weighted graph.
The main target of the algorithm is to find the subset of edges by using which we can traverse
every vertex of the graph. It follows the greedy approach that finds an optimum solution at every
stage instead of focusing on a global optimum.
How does Kruskal's algorithm work?
The steps to implement Kruskal's algorithm are listed as follows -
First, sort all the edges from low weight to high.
Now, take the edge with the lowest weight and add it to the spanning tree. If the edge to
be added creates a cycle, then reject the edge.
Continue to add the edges until we reach all vertices, and a minimum spanning tree is
created.
Now start with the following graph using Kruskal’s algorithm:
Solution:
Step 1:
Step 2:
Step 3:
Step 4 + 5:
Step 6:
Finally, Cost of MST = 7 + 3 + 3 + 2 + 2 = 17 units.
