Trees & Graphs

8 min readMar 10, 2023

What is a tree data structure?

A tree is a non-linear hierarchical data structure that has its applications in various areas. The top most node in a tree is called root. The left branch is called left subtree and the right is called right subtree. Each node that has children is called a parent node.

Let us understand the terms of tree in detail.

Root: The root of a tree is the topmost node of the tree that has no parent node. There is only one root node in every tree.
Parent Node: The node which is a predecessor of a node is called the parent node of that node.
Child Node: The node which is the immediate successor of a node is called the child node of that node.
Sibling: Children of the same parent node are called siblings.
Edge: Edge acts as a link between the parent node and the child node.
Leaf: A node that has no child is known as the leaf node. It is the last node of the tree. There can be multiple leaf nodes in a tree.
Subtree: The subtree of a node is the tree considering that particular node as the root node.
Depth: The depth of the node is the distance from the root node to that particular node.
Height: The height of the node is the distance from that node to the deepest node of that subtree.
Height of tree: The Height of the tree is the maximum height of any node. This is the same as the height of the root node.
Level: A level is the number of parent nodes corresponding to a given node of the tree.
Degree of node: The degree of a node is the number of its children.
NULL: The number of NULL nodes in a binary tree is (N+1), where N is the number of nodes in a binary tree.

A tree looks like this:

From the above diagram, we can see that 1 is the root of the tree. 2 and 3 are child nodes of parent 1 and are themselves parents for 4, 5 and 6, 7 respectively. The nodes 8, 9, 10, 11, 13, 14 are called leaf nodes.

Why Trees ?

We need to use a tree data structure when we want to store information that forms a hierarchy. An excellent example would be file system on a computer.
Accessing elements of a tree is faster than Linked lists but still slower than arrays.

Some applications of trees include:

1. Indexing in Databases.
2. Routing algorithms
3. Syntax analysis in Compilers

What is a binary tree?

A binary tree is a tree data structure in which each node can have at most two children, which are referred to as the left child and the right child. The topmost node in a binary tree is called the root, and the bottom-most nodes are called leaves. A binary tree can be visualized as a hierarchical structure with the root at the top and the leaves at the bottom.

Binary trees have many applications in computer science, including data storage and retrieval, expression evaluation, network routing, and game AI. They can also be used to implement various algorithms such as searching, sorting, and graph algorithms.

Representation of Binary Tree:

Each node in the tree contains the following:

Data
Pointer to the left child
Pointer to the right child

Basic Operations On Binary Tree:

Inserting an element.
Removing an element.
Searching for an element.
Deletion for an element.
Traversing an element. There are four (mainly three) types of traversals in a binary tree which will be discussed ahead.

Auxiliary Operations On Binary Tree:

Finding the height of the tree
Find the level of the tree
Finding the size of the entire tree.

Applications of Binary Tree:

In compilers, Expression Trees are used which is an application of binary trees.
Priority Queue is another application of binary tree that is used for searching maximum or minimum in O(1) time complexity.
Represent hierarchical data.
Used in editing software like Microsoft Excel and spreadsheets.
Useful for indexing segmented at the database is useful in storing cache in the system,
For implementing priority queues.
Used to find elements in less time (binary search tree)
Used to enable fast memory allocation in computers.
Used to perform encoding and decoding operations.
Binary trees can be used to represent the decision-making process of computer-controlled characters in games, such as in decision trees.
Binary trees can be used to implement searching algorithms, such as in binary search trees which can be used to quickly find an element in a sorted list.
Binary trees can be used to implement sorting algorithms, such as in heap sort which uses a binary heap to sort elements efficiently.

Binary Tree Traversals:

Tree Traversal algorithms can be classified broadly into two categories:

Depth-First Search (DFS) Algorithms
Breadth-First Search (BFS) Algorithms

Tree Traversal using Depth-First Search (DFS) algorithm can be further classified into three categories:

Preorder Traversal (current-left-right): Visit the current node before visiting any nodes inside the left or right subtrees. Here, the traversal is root — left child — right child. It means that the root node is traversed first then its left child and finally the right child.
Inorder Traversal (left-current-right): Visit the current node after visiting all nodes inside the left subtree but before visiting any node within the right subtree. Here, the traversal is left child — root — right child. It means that the left child is traversed first then its root node and finally the right child.
Postorder Traversal (left-right-current): Visit the current node after visiting all the nodes of the left and right subtrees. Here, the traversal is left child — right child — root. It means that the left child has traversed first then the right child and finally its root node.

Tree Traversal using Breadth-First Search (BFS) algorithm can be further classified into one category:

Level Order Traversal: Visit nodes level-by-level and left-to-right fashion at the same level. Here, the traversal is level-wise. It means that the most left child has traversed first and then the other children of the same level from left to right have traversed.

Let us traverse the following tree with all four traversal methods:

Binary Tree

Pre-order Traversal of the above tree: 1–2–4–5–3–6–7
In-order Traversal of the above tree: 4–2–5–1–6–3–7
Post-order Traversal of the above tree: 4–5–2–6–7–3–1
Level-order Traversal of the above tree: 1–2–3–4–5–6–7

Graphs:

A graph is a data structure for storing connected data such as a network of people on a social media platform.

A graph consists of vertices and edges. A vertex represents the entity (e.g., people) and an edge represents the relationship between entities (e.g., a person’s friendships).

Components of a Graph

Vertices: Vertices are the fundamental units of the graph. Sometimes, vertices are also known as vertex or nodes. Every node/vertex can be labeled or unlabelled.
Edges: Edges are drawn or used to connect two nodes of the graph. It can be ordered pair of nodes in a directed graph. Edges can connect any two nodes in any possible way. There are no rules. Sometimes, edges are also known as arcs. Every edge can be labeled/unlabelled.

Graphs are used to solve many real-life problems. Graphs are used to represent networks. The networks may include paths in a city or telephone network or circuit network. Graphs are also used in social networks like linkedIn, Facebook. For example, in Facebook, each person is represented with a vertex(or node). Each node is a structure and contains information like person id, name, gender, locale etc.

Types of Graph

Weighted Graph: In a weighted graph, each edge contains some data (weight) such as distance, weight, height, etc. It denoted as w(e). It is used to calculate the cost of traversing from one vertex to another. The following figure represents a weighted graph.

Unweighted Graph: A graph in which edges are not associated with any value is called an unweighted graph. The following figure represents an unweighted graph.

Directed Graph: A graph in which edges represent direction is called a directed graph. In a directed graph, we use arrows instead of lines (edges). Direction denotes the way to reach from one node to another node. Note that in a directed graph, we can move either in one direction or in both directions. The following figure represents a directed graph.

Undirected Graph: A graph in which edges are bidirectional is called an undirected graph. In an undirected graph, we can traverse in any direction. Note that we can use the same path for return through which we have traversed. While in the directed graph we cannot return from the same path.

Connected Graph: A graph is said to be connected if there exists at least one path between every pair of vertices. Note that a graph with only a vertex is a connected graph.

There are two types of connected graphs.

Weekly Connected Graph: A graph in which nodes cannot be visited by a single path is called a weekly connected graph.

Strongly Connected Graph: A graph in which nodes can be visited by a single path is called a strongly connected graph.

Disconnected Graph: A graph is said to be disconnected if there is no path between a pair of vertices is called a disconnected graph. A disconnected graph may consist of two or more connected graphs.

Multi Graph: A graph that has multiple edges connecting the same pair of nodes. The following figure represents a multi-graph.

Dense Graph: A graph in which the number of edges is close to the maximal number of edges, the graph is called the dense graph. The following figure represents a dense graph.

Sparse Graph: A graph in which the number of edges is close to the minimal number of edges, the graph is called the sparse graph. It can be a disconnected graph. The following figure represents a sparse graph.