Tree
The tree with no nodes is called the null or empty tree.
A tree that is not empty consists of a root node and potentially many levels of additional nodes that form a hierarchy.
Tree: undirected, connected graph with no cycles
Examples:
 The file system on the computer where we want to sort files by folder structure or size in the same folder.
 Manipulate hierarchical data.
 Make information easy to search
 Manipulate sorted lists of data.
 Multistage decisionmaking
 Authorization (e.g. Admin> All> RW> R)
 Javascript document object model

Time Complexity 
Space Complexity 

Average 
Worst 
Worst 

Data Structure 
Access 
Search 
Insertion 
Deletion 
Access 
Search 
Insertion 
Deletion 

Binary Search Tree 
Θ(log(n))  Θ(log(n))  Θ(log(n))  Θ(log(n))  O(n)  O(n)  O(n)  O(n)  O(n) 
Cartesian Tree 
N/A  Θ(log(n))  Θ(log(n))  Θ(log(n))  N/A  O(n)  O(n)  O(n)  O(n) 
BTree 
Θ(log(n))  Θ(log(n))  Θ(log(n))  Θ(log(n))  O(log(n))  O(log(n))  O(log(n))  O(log(n))  O(n) 
RedBlack Tree 
Θ(log(n))  Θ(log(n))  Θ(log(n))  Θ(log(n))  O(log(n))  O(log(n))  O(log(n))  O(log(n))  O(n) 
Splay Tree 
N/A  Θ(log(n))  Θ(log(n))  Θ(log(n))  N/A  O(log(n))  O(log(n))  O(log(n))  O(n) 
AVL Tree 
Θ(log(n))  Θ(log(n))  Θ(log(n))  Θ(log(n))  O(log(n))  O(log(n))  O(log(n))  O(log(n))  O(n) 
KD Tree 
Θ(log(n))  Θ(log(n))  Θ(log(n))  Θ(log(n))  O(n)  O(n)  O(n)  O(n)  O(n) 
Graph
Graph is a data structure that consists of following two components:
 A finite set of vertices also called as nodes.
 A finite set of ordered pair of the form (u, v) called as an edge.
 The pair is ordered because (u, v) is not same as (v, u) in the case of a directed graph(digraph).
 The pair of the form (u, v) indicates that there is an edge from vertex u to vertex v. The edges may contain weight/value/cost.
 V > Number of Vertices.
 E > Number of Edges.
Graph Classification:
The graph can be classified on the basis of many things, below are the two most common classifications:

Direction Graph:
 Undirected Graph: The graph in which all the edges are bidirectional.
 Directed Graph: The graph in which all the edges are unidirectional.

Weight Graph:
 Weighted Graph: The Graph in which weight is associated with the edges.
 Unweighted Graph: The Graph in which there is no weight associated with the edges.
Time Complexities:
 Time Complexities in a case of Adjacency Matrix:
 Traversal :(By BFS or DFS) O(V^2)
 Space: O(V^2)
 Time Complexities in the case of Adjacency List:
 Traversal :(By BFS or DFS) O(ElogV)
 Space: O(V+E)
Examples :
 Google map
 Represent network
 Telephone
 Social Networking sites
Representations of Graph:
 Adjacency Matrix
 It is a 2D array of size V x V where V is the number of vertices in a graph.
 Adjacency List
 Implemented using array of linked list.
 Size of the array is equal to number of vertices
 Used to represent a weighted graph
 Weights of edges can be stored in nodes of linked lists
 Incidence Matrix
 Incidence Lis