Trees
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.
trees-img-1.jpg
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.
trees-img-2.jpgtrees-img-3.jpg
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)
Output:
> Node 1
> 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);

  }
}
Output:
> Node 1
> 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);

  
}
Output:
> Node 1
> 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]));
Output:
> 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
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]);
    }

  }
}
Output:
> 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
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;
  }

  
}
Output:
> 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
You can play around with all the code we've used in this article on Replit:
Join our discord server for updates, announcements, future event planning, to ask questions, or just for fun!
Copyright ©2021 Howard County Hour of Code