Patterns to solve General Tree problems

What is a tree?

Tree data structure holds the following properties.

1. Tree has N nodes and all pairs are connected with N-1 edges.
2. Only one simple path between any pair of nodes.
3. Only one connected component and no cycle.

There are two types of trees.

1. Rooted: This means parent-child relationships are established.
2. Unrooted: It means no relationships between nodes are defined.

Find out the properties of each node

Let’s try to find the properties of each node.

1. Is it a leaf node?
2. What is the depth of the node?
3. How many nodes are in the subtree?
4. How many children of the node?
5. What is the parent of the node?

Let’s use dfs to find these properties.

// tree representation as undirected graph edge list
const tree = [];
const n = tree.length;
const depth = new Array(n).fill(0);
const parent = new Array(n).fill(-1);
const leaf = new Array(n).fill(false);
const subtree = new Array(n).fill(0);
const children = new Array(n).fill(0);
const dfs = (node) => {
    children[node] = 0;
    subtree[node] = 1;
    for (const child of tree[node]) { 
      if(child != parent[node]) {  // parent check to handle undirected (v->u & u-> v)
        // in-order processing for children and parent
        children[node]++; 
        parent[child] = node;
        depth[child] = depth[node] + 1;
        dfs(child); 
        // post-order processing for subtree
        subtree[node]+= subtree[child]; // At this moment, child's subtree would have calculated
      }
    }
    // post-order of node for leaf node
    leaf[node] = !!children[node];
    
}
dfs(0);

Note: Since the tree has only one path therefore both dfs and bfs gives the same shortest path. Therefore both provide the same result.

We can use the above code to answer many tree-related questions as below.

Distance/Path between u and v

1. Run dfs(u) i.e. run the traversal algorithm keeping u as root.

2. distance = depth[v] — depth[u] will give the shortest path. Since a tree has only one path there is no need to run bfs .

3. Similarly, keep traversing parent[v] until find u to get the path.

Length of the Diameter of tree

1. For any random node x find out the farthest node y . This will give the one end of the diameter.
2. From node y find out the farthest node z . This will give the other end of the diameter.
3. Path between y and z will be the diameter of the tree.

Note: The diameter of the tree is not a unique path. There could be multiple diameters in a tree.

Following is the code to implement this.

// tree representation as undirected graph edge list
const tree = [];
const n = tree.length;
let parent = new Array(n).fill(-1);
let depth = new Array(n).fill(0);
const dfs = (node) => {
    for (const child of tree[node]) { 
      if(child != parent[node]) {  // parent check to handle undirected (v->u & u-> v)
          parent[child] = node;
          depth[child] = depth[node] + 1;  
          dfs(child); 
      }
    }
    
}
const getFarthestNode = root => { // Get the index of largest depth
  let maxNode = root;
  for (let i=0; i < n; i++) {
    if(depth[i] > depth[maxNode]) {
      maxNode = i;
    }
  }
  return maxNode;
}
// Choose root=0
dfs(0);
// Find farthest node from root
const yNode = getFarthestNode(0);
// Now run dfs one more time on farthest node
depth = new Array(n).fill(0);
parent = new Array(n).fill(-1);
dfs(yNode);
// Ans will be next farthest node
const zNode = getFarthestNode(yNode);
return depth[zNode];

Minimum time to traverse the whole non rooted tree

Q1. Minimum time to traverse a non rooted tree is to start from any node and return to the same node.

Ans. In this case, ans will be 2*E i.e. 2*(n-1) .

Q2. Minimum time to traverse a non rooted tree to start from any node (not necessarily come back to the same node).

Ans. In this case, we save the path to return to the starting node compared to Q1. I.e. time to traverse will be 2*E-path where path is one such possible path to return to the same node before we complete the traversal.

So to find out the minimum time to traverse a non rooted tree, we need the maximum value for path which will be the diameter of the tree.

I.e., the minimum time to traverse a nonrooted tree to start from any node would be 2*E — Diameter

The center node of the tree

Q. Is the center a property of the tree or diameter? I.e. will the center change if more diameters are discovered?

Ans. The tree's center doesn’t change irrespective of which diameter you choose. The center is fixed for the tree. All the diameters will have the same center.

• There are at max two centers in the tree. Odd length vs even length.
• Every diameter passes through the center of the tree.
• We can find out the center from one diameter and then make sure all other diameter passes through that.

Find the number of diameters in a tree

1. Find a single diameter of a tree.
2. Traverse D/2 to find out the first center in case of even. If odd then there would be a second center as the next node.
3. Count the number of diameters for the following example.

Use case 1: Single-center

1. From the center, in each of the branches, count the node at a distance (D/2) — 1

2. Summation of all pair products will give the count of diameters.

3. To find the number of nodes, find the size of the subtree of each child.

Use case 2: Two centers

1. Find out the size of the subtree for each center.
2. You may want to run dfs(root, blocked,-1) pattern for each center to make sure when it runs on the first center it doesn’t traverse the second center.

Centroid of the tree

The centroid is the node of the tree's size N such that if you root that node then each of the subtrees will have <= N/2 nodes.

Q. Will there be only one centroid?

Ans. No. There could be multiple. At most trees can have two centroids.

Q. Are the center and centroid the same?

Ans. No

How to find the centroid?

1. For a given node, if it is not a centroid then one of the subtrees must be >N/2 .

2. It also means, the centroid will exist in the subtree with >=N/2

3. Then try the node with a subtree >=N/2 and calculate the all subtree size. If it satisfies <=N/2 then the node is centroid otherwise recursively moves to subtree with >N/2 nodes.

4. Start with a random node.

Distance of all pair nodes

We can run dfs(a,b) on all pairs of nodes and sum the distance. Time complexity will be O(n*n*n) . Can we do better?

Contribution technique

1. We can sum the distance of each pair of nodes.
2. Each distance is nothing but the count of edges.
3. Edges gets repeated
4. If we can count how many times the edge appears in the all-pair sum then we can answer it.
5. For each edge, we can find out the subtree size then multiplications of these will us how many times an edge will be part of the path.

6. For every edge, find out the count and sum it.

7. For each edge u->v, count will be (subtree[u])*(n — subtree[u]) . Once we calculate subtree of u then subtree of v will be n — subtree(u)

Time complexity would be O(n) .

Maximum absolute difference with ancestor for weighted tree

1. For every dfs() path, keep track of minimum node weight and maximum node weight.
2. Handle answer for root separately.
3. Along with dfs we need to maintain a multiset to track the answer.

1443. Minimum Time to Collect All Apples in a Tree

https://leetcode.com/problems/minimum-time-to-collect-all-apples-in-a-tree/description

Given an undirected tree consisting of n vertices numbered from 0 to n-1, which has some apples in their vertices. You spend 1 second to walk over one edge of the tree. Return the minimum time in seconds you have to spend to collect all apples in the tree, starting at vertex 0 and coming back to this vertex.

The edges of the undirected tree are given in the array edges, where edges[i] = [ai, bi] means that exists an edge connecting the vertices ai and bi. Additionally, there is a boolean array hasApple, where hasApple[i] = true means that vertex i has an apple; otherwise, it does not have any apple.

Example 1:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false]
Output: 8

Approach

1. If all tree has apple then task is nothing but to run the Eular tour code.
2. If a child doesn’t have apple still we would explore subtree and try to pick apple.
3. If subtree doesn’t have apple then only we will discard that specific branch.
4. It means dfs() needs to return true/false if subtree has apple or not.
5. If dfs() return true then only we should count the time.

Following is code for reference.

/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {boolean[]} hasApple
 * @return {number}
 */
var minTime = function (n, edges, hasApple) {
    let ans = 0;
    const tree = new Array(n).fill(0).map(a => []);
    const visited = new Array(n).fill(false);
    for (const [u, v] of edges) {
        tree[u].push(v);
        tree[v].push(u);
    }
    const dfs = node => {
        visited[node] = true;
        let subtreeHasApple = false;
        for (const neighbor of tree[node]) {
            if (!visited[neighbor]) {
                if (dfs(neighbor)) {
                    subtreeHasApple = true;
                    ans += 2;
                }

            }
        }
        return subtreeHasApple || hasApple[node];
    }
    dfs(0);
    return ans;
};

This blog is based on the Tree course taught at https://maang.in. The instructor is simply great. Feel free to buy this course :-)