Trees
15pts
Python
Java
C++
Algorithms
Data
What is a tree and how is it used
Trees are a specific type of graph. Formally, a tree is a
connected graph consisting of N nodes and N-1 edges. A defining
feature of a tree is having no cycles (i.e. acyclic). If an edge is
added to a tree, a cycle will be created, since a graph with as many
edges as nodes must have at least one cycle. In addition, removing
any edge from a tree will divide it into two separate components.
The degree of a node in a graph is defined as the number of
nodes that it is connected to (its neighbors).
The leaves of a tree are the nodes with a degree of 1 (i.e.
only one neighbor).
This counts as a tree because there are 5 nodes, 4 edges, and no
cycles.
The below example is not a tree because it has a cycle with nodes 2,
4, and 5. If the edge from node 4 to node 5 is removed, the graph
would become a tree.
In a rooted tree, the children of a node are its lower neighbors,
and the parent of a node is its upper neighbors. Every node has
exactly one parent besides the root, which doesn’t have a parent.
For example, the parent of node 5 is 2. However, a node can have
multiple children. The children of node 2 are 4 and 5.
It is important to understand that the structure of a tree acts
recursively. In other words, each node of the tree could be viewed
as the root of a subtree that contains all the nodes
underneath that node. For instance, the subtree of node 2 in the
example above would consist of nodes 2, 4, and 5. The subtree of
node 3 would consist only of node 3, and the subtree of node 1 would
consist of nodes 1, 2, 3, 4, and 5.
Trees can be traversed using standard graph traversal techniques
such as DFS (depth-first search) and BFS (breadth-first search). We
will go over the DFS traversal, starting from the root node.
For these examples, we will represent the graph pictured above.
Code:
numberNodes=5
edges = [[False]*(numberNodes+1) for i in range(numberNodes+1)]
visited = [False] * (numberNodes+1)
# adding edges to graph with an adjacency matrix
edges[1][2] = True
edges[2][1] = True
edges[1][3] = True
edges[3][1] = True
edges[2][4] = True
edges[4][2] = True
edges[2][5] = True
edges[5][2] = True
def dfs(node):
visited[node]=True;
# printing current node
print("Node " + str(node))
for u in range(numberNodes+1):
if edges[node][u] and not visited[u]:
# recursively visiting children nodes
dfs(u)
# started at the root node 1
dfs(1)
> Node 1
> Node 2
> Node 4
> Node 5
> Node 3
> Node 2
> Node 4
> Node 5
> Node 3
Code:
import java.util.ArrayList;
public class Main {
static int numberNodes=5;
static boolean[] visited = new boolean[numberNodes+1];
static ArrayList> edges = new ArrayList>(numberNodes+1);
public static void dfs(int node){
visited[node]=true;
// printing current node
System.out.println("Node "+node);
for (Integer u: edges.get(node)){
if (!visited[u]){
// recursively visiting children nodes
dfs(u);
}
}
}
public static void main(String[] args) {
// adding edges to graph with an adjacency list
for (int i=0; i());
}
edges.get(1).add(2);
edges.get(2).add(1);
edges.get(1).add(3);
edges.get(3).add(1);
edges.get(2).add(4);
edges.get(4).add(2);
edges.get(2).add(5);
edges.get(5).add(2);
// starting at the root node 1
dfs(1);
}
}
> Node 1
> Node 2
> Node 4
> Node 5
> Node 3
> Node 2
> Node 4
> Node 5
> Node 3
Code:
#include <bits/stdc++.h>
using namespace std;
const int numberNodes=5;
bool visited[numberNodes+1]={0};
vector edges[numberNodes+1];
void dfs(int node){
visited[node]=true;
// printing current node
cout << "Node " << node << endl;
for (auto u: edges[node]){
if (!visited[u]){
// recursively visiting children nodes
dfs(u);
}
}
}
int main() {
// adding edges to graph with an adjacency list
edges[1].push_back(2);
edges[2].push_back(1);
edges[1].push_back(3);
edges[3].push_back(1);
edges[2].push_back(4);
edges[4].push_back(2);
edges[2].push_back(5);
edges[5].push_back(2);
// starting at the root node 1
dfs(1);
}
> Node 1
> Node 2
> Node 4
> Node 5
> Node 3
> Node 2
> Node 4
> Node 5
> Node 3
Note: the implementation in Python uses an
adjacency matrix to store the edges, while the implementation
in Java and C++ uses an adjacency list to store the edges. An
adjacency matrix is a N by N matrix where each cell is either
true or false depending on if an edge exists between nodes i and
nodes j. An adjacency list is a collection of N lists (one
for each node) that contain the nodes that are adjacent or connected
to a given node.
One well-known tree problem is calculating the size of each node’s
subtree. This can be done by going through the tree with a DFS
traversal, and recursively calculating the subtree size of each
node’s children. Then, we just add the subtree size of each node’s
children to the current node. The key is to initialize each node’s
subtree size as 1 when that node is visited.
Code:
numberNodes=5
edges = [[False]*(numberNodes+1) for i in range(numberNodes+1)]
visited = [False] * (numberNodes+1)
subtreeSize = [0] * (numberNodes+1)
# adding edges to graph with an adjacency matrix
edges[1][2] = True
edges[2][1] = True
edges[1][3] = True
edges[3][1] = True
edges[2][4] = True
edges[4][2] = True
edges[2][5] = True
edges[5][2] = True
def dfs(node):
visited[node]=True;
# initializing subtree size to 1
subtreeSize[node]=1
for u in range(numberNodes+1):
if edges[node][u] and not visited[u]:
# recursively visiting children nodes
dfs(u)
# adding children's subtree size to current node's subtree size
subtreeSize[node]+=subtreeSize[u]
# started at the root node 1
dfs(1)
for i in range(1, numberNodes+1):
print("Node: "+ str(i) +" Subtree Size: "+ str(subtreeSize[i]));
> Node: 1 Subtree Size: 5
> Node: 2 Subtree Size: 3
> Node: 3 Subtree Size: 1
> Node: 4 Subtree Size: 1
> Node: 5 Subtree Size: 1
> Node: 2 Subtree Size: 3
> Node: 3 Subtree Size: 1
> Node: 4 Subtree Size: 1
> Node: 5 Subtree Size: 1
Code:
import java.util.ArrayList;
public class Main {
static int numberNodes=5;
static boolean[] visited = new boolean[numberNodes+1];
static ArrayList> edges = new ArrayList>(numberNodes+1);
static int[] subtreeSize = new int[numberNodes+1];
public static void dfs(int node){
visited[node]=true;
// initializing subtree size to 1
subtreeSize[node]=1;
for (Integer u: edges.get(node)){
if (!visited[u]){
// recursively visiting children nodes
dfs(u);
// adding children's subtree size to current node's subtree size
subtreeSize[node]+=subtreeSize[u];
}
}
}
public static void main(String[] args) {
// adding edges to graph with an adjacency list
for (int i=0; i());
}
edges.get(1).add(2);
edges.get(2).add(1);
edges.get(1).add(3);
edges.get(3).add(1);
edges.get(2).add(4);
edges.get(4).add(2);
edges.get(2).add(5);
edges.get(5).add(2);
// starting at the root node 1
dfs(1);
for (int i=1; i<=5; i++){
System.out.println("Node: "+ i +" Subtree Size: "+ subtreeSize[i]);
}
}
}
> Node: 1 Subtree Size: 5
> Node: 2 Subtree Size: 3
> Node: 3 Subtree Size: 1
> Node: 4 Subtree Size: 1
> Node: 5 Subtree Size: 1
> Node: 2 Subtree Size: 3
> Node: 3 Subtree Size: 1
> Node: 4 Subtree Size: 1
> Node: 5 Subtree Size: 1
Code:
#include <bits/stdc++.h>
using namespace std;
const int numberNodes=5;
bool visited[numberNodes+1]={0};
vector edges[numberNodes+1];
int subtreeSize[numberNodes+1]={0};
void dfs(int node){
visited[node]=true;
// initializing subtree size to 1
subtreeSize[node]=1;
for (auto u: edges[node]){
if (!visited[u]){
// recursively visiting children nodes
dfs(u);
// adding children's subtree size to current node's subtree size
subtreeSize[node]+=subtreeSize[u];
}
}
}
int main() {
// adding edges to graph with an adjacency list
edges[1].push_back(2);
edges[2].push_back(1);
edges[1].push_back(3);
edges[3].push_back(1);
edges[2].push_back(4);
edges[4].push_back(2);
edges[2].push_back(5);
edges[5].push_back(2);
// started at the root node 1
dfs(1);
for (int i=1; i<=5; i++){
cout << "Node: " << i << " Subtree Size: " << subtreeSize[i] << endl;
}
}
> Node: 1 Subtree Size: 5
> Node: 2 Subtree Size: 3
> Node: 3 Subtree Size: 1
> Node: 4 Subtree Size: 1
> Node: 5 Subtree Size: 1
> Node: 2 Subtree Size: 3
> Node: 3 Subtree Size: 1
> Node: 4 Subtree Size: 1
> Node: 5 Subtree Size: 1
You can play around with all the code we've used in this article on
Replit: