IPU Computer Science - Discrete Mathematics - Trees vs Graphs

Trees vs Graphs

	Trees	Graphs
Shape
Model Type	Hierarchical	Network
No. Of Edges	n-1 edges	Depends on graph shape
Path	Minimally connected graph, contains only one path between any two vertices.	More than one path possible. Can be uni-directional or bi-directional.
Root Node	One Root, Child has one Parent	No concept of Root or Parent
Parent Child Relationship	Parent Child relationship when moves from top to bottom.	No such concept of parent child relationship.
Loops	Special type of graph having no loops or circuits.	Have loops, circuits and self-loops
Traversal	Pre-Order, In-Order and Post-Order	Depth First Search (DFS) or Breadth First Search (BFS)
Connecting Rules	Restrictions for making connection between nodes through edges.	As such no restrictions while connecting edges and nodes.
Direction	Directed Acyclic Graph	Cyclic or Acyclic
Complexity	Less complex as compared to graphs. No loops, no cycles etc.	More complex as it contains loops, cycles etc.
Types	Binary Tree, Binary Search Tree, AVL Tree, Heaps etc.	Directed and Undirected graphs
Applications	Used in sorting and searching like tree traversing, binary search. Manipulate hierarchical data	PERT or CPM algorithms, Graph colouring, job scheduling etc.