Concepts of graphs and trees in computers:
A graph consists of nodes (vertices) and edges that connect these nodes. Graphs can be directed (edges have
a direction) or undirected (edges have no direction). There are several ways to represent graphs in
computers.
Graph:
A graph is a collection of two sets V and E where V is a finite non-empty set of vertices and E is a
finite non-empty set of edges.
Vertices are nothing but the nodes in the graph.
Two adjacent vertices are joined by edges.
Any graph is denoted as G = {V, E}.
For Example:
G = {{V1, V2, V3, V4, V5, V6}, {E1, E2, E3, E4, E5, E6, E7}}
A graph is a collection of vertices (also known as nodes) and edges that connect these vertices. Each
edge represents a relationship or connection between two vertices.
Graphs can be directed or undirected, meaning that edges have a specific direction or they do not.
A directed graph is also known as a digraph. Graphs can also have weighted edges, where each edge
has a weight or cost associated with it. Graphs can be represented in various ways, such as adjacency
matrix or adjacency list.
Tree:
A tree is a special type of graph that is connected and acyclic, meaning that there are no cycles in the
graph. In a tree, there is a unique path between any two vertices, and there is a single vertex called the
root that is used as the starting point for traversing the tree. Trees can be used to model hierarchical
relationships, such as the structure of a file system or the organization of a company. Trees can be binary
or non-binary. In a binary tree, each node has at most two children, while in a non-binary tree, each node
can have any number of children. Binary trees can be used to solve problems such as searching and
sorting, as well as to represent expressions and parse trees.
A tree is a finite set of one or more nodes such that –
1. There is a specially designated node called root.
2. The remaining nodes are partitioned into n>=0 disjoint sets T 1, T2, T3, …, Tn
where T1, T2, T3, …, Tn are called the subtrees of the root.
The concept of a tree is represented by following Fig.
Binary search tree:
Given a Binary Search Tree, the task is to print the elements in inorder, preorder, and postorder
traversal of the Binary Search Tree.
Output:
Inorder Traversal: 10 20 30 100 150 200 300
Preorder Traversal: 100 20 10 30 200 150 300
Postorder Traversal: 10 30 20 150 300 200 100
Inorder Traversal:
Below is the idea to solve the problem:
At first traverse left subtree then visit the root and then traverse the right subtree.
Follow the below steps to implement the idea:
Traverse left subtree
Visit the root and print the data.
Traverse the right subtree
The inorder traversal of the BST gives the values of the nodes in sorted order. To get the decreasing
order visit the right, root, and left subtree.
Below is the implementation of the inorder traversal.
# Python code to implement the approach
# Class describing a node of tree
class Node:
def __init__(self, v):
self.left = None
self.right = None
self.data = v
# Inorder Traversal
def printInorder(root):
if root:
# Traverse left subtree
printInorder(root.left)
# Visit node
print(root.data,end=" ")
# Traverse right subtree
printInorder(root.right)
# Driver code
if __name__ == "__main__":
# Build the tree
root = Node(100)
root.left = Node(20)
root.right = Node(200)
root.left.left = Node(10)
root.left.right = Node(30)
root.right.left = Node(150)
root.right.right = Node(300)
# Function call
print("Inorder Traversal:",end=" ")
printInorder(root)
Output
Inorder Traversal: 10 20 30 100 150 200 300
Time complexity: O(N), Where N is the number of nodes.
Auxiliary Space: O(h), Where h is the height of tree
Preorder Traversal:
Below is the idea to solve the problem:
At first visit the root then traverse left subtree and then traverse the right subtree.
Follow the below steps to implement the idea:
Visit the root and print the data.
Traverse left subtree
Traverse the right subtree
Below is the implementation of the preorder traversal.
class Node:
def __init__(self, v):
self.data = v
self.left = None
self.right = None
# Preorder Traversal
def printPreOrder(node):
if node is None:
return
# Visit Node
print(node.data, end = " ")
# Traverse left subtree
printPreOrder(node.left)
# Traverse right subtree
printPreOrder(node.right)
# Driver code
if __name__ == "__main__":
# Build the tree
root = Node(100)
root.left = Node(20)
root.right = Node(200)
root.left.left = Node(10)
root.left.right = Node(30)
root.right.left = Node(150)
root.right.right = Node(300)
# Function call
print("Preorder Traversal: ", end = "")
printPreOrder(root)
Output
Preorder Traversal: 100 20 10 30 200 150 300
Time complexity: O(N), Where N is the number of nodes.
Auxiliary Space: O(H), Where H is the height of the tree
Postorder Traversal:
Below is the idea to solve the problem:
At first traverse left subtree then traverse the right subtree and then visit the root.
Follow the below steps to implement the idea:
Traverse left subtree
Traverse the right subtree
Visit the root and print the data.
Below is the implementation of the postorder traversal:
class Node:
def __init__(self, v):
self.data = v
self.left = None
self.right = None
# Preorder Traversal
def printPostOrder(node):
if node is None:
return
# Traverse left subtree
printPostOrder(node.left)
# Traverse right subtree
printPostOrder(node.right)
# Visit Node
print(node.data, end = " ")
# Driver code
if __name__ == "__main__":
# Build the tree
root = Node(100)
root.left = Node(20)
root.right = Node(200)
root.left.left = Node(10)
root.left.right = Node(30)
root.right.left = Node(150)
root.right.right = Node(300)
# Function call
print("Postorder Traversal: ", end = "")
printPostOrder(root)
Output
PostOrder Traversal: 10 30 20 150 300 200 100
Time complexity: O(N), Where N is the number of nodes.
Auxiliary Space: O(H), Where H is the height of the tree
