# Dstl notes Trees, Graph and combinatorics in Discrete mathematics Aktu notes

__Trees Graphs and Combinatorics__

__Syllabus (Topic cover in this section):__

**TREES: Definitions**,

**Binary tree,**

**Binary tree traversal,**

**Binary search tree,**

**GRAPHS: Definitions and terminology,**

**Representation of graphs,**

**Multigraph,**

**Bipartite Graphs,**

**Planar graphs,**

**Isomorphism and Homomorphisms of the graph,**

**Euler and Hamiltonian paths,**

**Graph Coloring,**

**Recurrence Relation & Generating Function: Recursive definition of function,**

**Recursive Algorithms,**

**Method of solving recurrences.**

**COMBINATORICS: Introduction,**

**Counting Techniques,**

**Pigeonhole Principle.**

**( Note:- Please check all kinds of information as per your college/university curriculum because it can be updated syllabus from time to time. )**

** **

**Tree: **

**vertices**or

**nodes**.

**Forest:**

**Binary tree in discrete structure:**

**Complete binary tree in discrete structure:**

**Full binary tree:**

**Tree Traversal:**

**1.Preorder traversal**

- Visit the root(N).
- Visit the left child (or subtree) of the root(L).
- Visit the right child (or subtree) of the root (R).

**2.Inorder traversal**

- Visit the left child (subtree) of the tree.
- Visit the root.
- Visit the right child (subtree) of the root.

**3.Postorder traversal**

- Visit the left child (subtree) of the root.
- Visit the right child (subtree) of the root.
- Visit the root.

**What is a binary search tree?**

- A binary search tree is a binary tree T in which data is associated with the vertices.
- The data are arranged so that, for each vertex v in T, each data item in the left subtree of v is less than the data item in v each data item in the right subtree of v is greater than the data item in v.
- In a binary search tree since every vertex in T exceeds every number in its left subtree and is less than every number in its right subtree.

**In other words,**

**A binary tree has the following time complexities…**

- Search Operation – O(n)
- Insertion Operation – O(1)
- Deletion Operation – O(n)

**Operations on a Binary Search Tree**

- Search
- Insertion
- Deletion

**Search Operation in BST**

Step 1 – Read the search element from the user.

Step 2 – Compare the search element with the value of the root node in the tree.

Step 3 – If both are matched, then display “Given node is found!!!” and terminate the function

Step 4 – If both are not matched, then check whether the search element is smaller or larger than that node value.

Step 5 – If the search element is smaller, then continue the search process in the left subtree.

Step 6- If the search element is larger, then continue the search process in the right subtree.

Step 7 – Repeat the same until we find the exact element or until the search element is compared with the leaf node

Step 8 – If we reach the node having the value equal to the search value then display “Element is found” and terminate the function.

Step 9 – If we reach the leaf node and if it is also not matched with the search element, then display “Element is not found” and terminate the function.

**Difference between BFS and DFS**

**Breadth-First Search (BFS)**

**Algorithmic Steps:**

**Step 1:**Push the root node in the queue.

**Step 2:**Loop until the queue is empty.

**Step 3:**Remove the node from the queue.

**Step 4:**If the removed node has unvisited child nodes, mark them as visited and insert the unvisited children in the queue.

**Depth First Search (DFS)**

### Algorithmic Step:

**Step 1:**Push the root node in the stack.

**Step 2:**Loop Until the stack is empty.

**Step 3:**Pick the node on the stack.

**Step 4:**If the node has an unvisited child node, get the unvisited child node, mark it as traversed, and push it on the stack.

**Step 5:**If the node does not have any unvisited child nodes, pop the node from the stack.

## Define Graph

**For example:**

**Order of Graph (G)**

**Size of Graph (G)**

**Difference between Directed and Undirected Graph**

#### Directed Graph: A directed graph is a set of vertices (nodes) connected by edges, with each node having a direction associated with it. Edges are usually represented by arrows pointing in the direction the graph can be traversed.

**In other words**, A Graph G(V, E) is said to be a directed graph or digraph if each edge e belongs to E is associated with an ordered pair of vertices as shown below:

** **