Hi, all Welcome to Session 7. This will the last session of Level 1 and we will be winding up this with some discussion on Tree. Things that will be discussed here.
That's all for this article, now before proceeding to the next Level-2, solve all practice problems ( If you stuck then do comment Question Number for Solution and your approach so that other programmer or we can help you).
- Introduction to Tree
- Tree Traversal
- Counting the number of nodes in Subtree
- The diameter of a Tree
- Longest path distance from each node.
- Practice Problems
Introduction to Tree
A tree is a connected, acyclic graph that consists of N nodes and N-1 edges. The tree is a special case of Graphs (ie. it is a graph with Restriction). Some of the things that can be observed in a tree are
- If we remove any edge in the tree then the number of the component will increase.
- Adding an extra edge to the tree will introduce cycles.
Fig 1: Tree with 11 Nodes
Some terminology
Leaf Node: node with degree 1 is called the leaf node, here 7, 8, 9, 10, 11 are leaf node. In other words, we can also say that node which have only one adjacent node or neighboring node.
- Rooted Tree: In a rooted tree, we have one node as root and all other nodes are placed below the root. In Fig 1 we have 1 as the root of the tree.
- In a rooted tree, we have parent-child relation, ie. the neighbor which is placed below the given node is its child and the one placed above it is the parent. Here if we take node 2 then it's the parent is 1 and child nodes are 4,5.
- And 2 is a parent of child nodes are 4,5.
- Subtree
- The rooted tree is recursive ie. every node act as a root of the subtree that contains this element and all other children nodes. ie, 2 if a root for subtree with element { 2, 4, 5, 8, 9, 10, 11 }.
Tree Traversal
As we have discussed earlier in this section the Tree is a special case of Graphs and hence we can use the Graph Traversal algorithm which has been discussed earlier in this Series.
The implementation of tree traversal is easier for the Tree as we don't have a cycle and hence no multiple paths between any pair of vertices.
Counting the number of nodes in a Subtree.
This is a simple problem from rooted trees, here we just need to count the number of nodes in a subtree. Things we have to care about.
- The leaf node is a subtree with one node and that is itself.
- Any other subtree has more than 1 node.
- For this, we will be using the Depth-first Search algorithm
- The running time of the algorithm for n nodes is O(n) as O(n+n-1) = O(n) where n-1 is the number of edges.
- Representation for the tree is Adjacency List.
- Here the root of the tree is 1.
- Implementation
#include <bits/stdc++.h> #define ll long long int #define mod 1000000007 using namespace std;
void dfs(bool visited[], int counts[], vector<int> adj[], int s) { visited[s] = true; counts[s] = 1; for (auto u : adj[s]) { if (visited[u]) continue; visited[u] = true; dfs(visited, counts, adj, u); counts[s] += counts[u]; } }
void solve() { int n; cin >> n; // n-number of nodes in subtree. vector<int> adj[n + 1]; for (int i = 1; i < n; i++) { // number of edges in tree = nodes - 1 int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); }
bool visited[n + 1]; memset(visited, false, sizeof visited); int counts[n + 1];
// calling dfs on root node 1. dfs(visited, counts, adj, 1);
cout << "Subtree roots: "; for (int i = 1; i <= n; i++) cout << i << " "; cout << "\n"; cout << "Num. of nodes: "; for (int i = 1; i <= n; i++) cout << counts[i] << " "; cout << "\n"; }
int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); return 0; }
#include <bits/stdc++.h>
#define ll long long int
#define mod 1000000007
using namespace std;
void dfs(bool visited[], int counts[], vector<int> adj[], int s) {
visited[s] = true;
counts[s] = 1;
for (auto u : adj[s]) {
if (visited[u])
continue;
visited[u] = true;
dfs(visited, counts, adj, u);
counts[s] += counts[u];
}
}
void solve() {
int n;
cin >> n; // n-number of nodes in subtree.
vector<int> adj[n + 1];
for (int i = 1; i < n; i++) { // number of edges in tree = nodes - 1
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
bool visited[n + 1];
memset(visited, false, sizeof visited);
int counts[n + 1];
// calling dfs on root node 1.
dfs(visited, counts, adj, 1);
cout << "Subtree roots: ";
for (int i = 1; i <= n; i++)
cout << i << " ";
cout << "\n";
cout << "Num. of nodes: ";
for (int i = 1; i <= n; i++)
cout << counts[i] << " ";
cout << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
Input:
6
1 2
2 3
3 4
4 5
4 6
Output:
Subtree roots: 1 2 3 4 5 6
Num. of nodes: 6 5 4 3 1 1
Finding Diameter of Tree
The Diameter of a tree is the maximum length of the path between two nodes.
Fig 2: Tree
In fig 2 we have a diameter of length 4 which is the path between 1,5 or 1,6. Now we need to find the diameter of a tree so what we can do here.
- So to solve this problem let us take any arbitrary node (Say 4), run DFS and find the node which is farthest from it (running DFS at node 4 will give 1 to be the farthest node (path length=3 )).
- After getting the farthest node run DFS again at that node and find the farthest node from it (here it will be 5 and 6 both at distance 4 ).
- And hence we have got the solution by running DFS 2 times
- The running time of the algorithm for n nodes is O(n) as O(n+n-1) = O(n) where n-1 is the number of edges.
- This can also be solved by BFS (Breadth-first search algorithm) with same cost.
- Implementation
#include <bits/stdc++.h> #define ll long long int #define mod 1000000007 using namespace std;
int dist[100001]; // Initialized for 10^5 nodes.
void dfs(bool visited[], vector<int> adj[], int s) { visited[s] = true; for (auto u : adj[s]) { if (visited[u]) continue; visited[u] = true; dist[u] = dist[s] + 1; dfs(visited, adj, u); } }
void solve() { int n; cin >> n; // n-number of nodes in subtree. vector<int> adj[n + 1]; for (int i = 1; i < n; i++) { // number of edges in tree = nodes - 1 int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); }
bool visited[n + 1]; memset(visited, false, sizeof visited); for (int i = 1; i <= n; i++) dist[i] = 0; // calling dfs to get farthest node from any node (say 4). dfs(visited, adj, 4); int farthest_vertex = 0, dis = 0; for (int i = 1; i <= n; i++) { if (dis < dist[i]) { dis = dist[i]; farthest_vertex = i; } }
// cout<<"Farthest vertex: "<<farthest_vertex<<"\n"; // calling dfs from the farthest_vertex. memset(visited, false, sizeof visited); for (int i = 1; i <= n; i++) dist[i] = 0; dfs(visited, adj, farthest_vertex);
// Now the max distace which we will get will be the diameter. int diameter = 0; for (int i = 1; i <= n; i++) diameter = max(diameter, dist[i]);
cout << "The diameter of given tree is: " << diameter << "\n"; }
int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); return 0; }
#include <bits/stdc++.h>
#define ll long long int
#define mod 1000000007
using namespace std;
int dist[100001]; // Initialized for 10^5 nodes.
void dfs(bool visited[], vector<int> adj[], int s) {
visited[s] = true;
for (auto u : adj[s]) {
if (visited[u])
continue;
visited[u] = true;
dist[u] = dist[s] + 1;
dfs(visited, adj, u);
}
}
void solve() {
int n;
cin >> n; // n-number of nodes in subtree.
vector<int> adj[n + 1];
for (int i = 1; i < n; i++) { // number of edges in tree = nodes - 1
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
bool visited[n + 1];
memset(visited, false, sizeof visited);
for (int i = 1; i <= n; i++)
dist[i] = 0;
// calling dfs to get farthest node from any node (say 4).
dfs(visited, adj, 4);
int farthest_vertex = 0, dis = 0;
for (int i = 1; i <= n; i++) {
if (dis < dist[i]) {
dis = dist[i];
farthest_vertex = i;
}
}
// cout<<"Farthest vertex: "<<farthest_vertex<<"\n";
// calling dfs from the farthest_vertex.
memset(visited, false, sizeof visited);
for (int i = 1; i <= n; i++)
dist[i] = 0;
dfs(visited, adj, farthest_vertex);
// Now the max distace which we will get will be the diameter.
int diameter = 0;
for (int i = 1; i <= n; i++)
diameter = max(diameter, dist[i]);
cout << "The diameter of given tree is: " << diameter << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
Input:
6
1 2
2 3
3 4
4 5
4 6
Output:
The diameter of given tree is: 4
Longest path distance from each node.
This problem simply says us to find the distance of the farthest vertex from each node. From Fig 2 we can have
Fig 3: Longest path distance from each node in Fig 2.
This can also be implemented in a same way as we have done for diameter of the tree. We believe that you can implement this on your own.
Practice Problem
That's all for this article, now before proceeding to the next Level-2, solve all practice problems ( If you stuck then do comment Question Number for Solution and your approach so that other programmer or we can help you).
If you have some content OR material related to this then do share them through the comment section for which we will be thankful to you.
Thank You
With 💙 by Learn DSA