CODEWITHSUNDEEP
algorithm
quantumbutterfly
quantumbutterfly

Reputation: 1953

Algorithm for finding the size of the largest connected region of nodes of the same value in a tree

This is a question I got in an interview, and I'm still not fully sure how to solve it.

Let's say we have a tree of numbers, and we want to find the size of the largest connected region in the tree whose nodes have the same value. For example, in this tree

    3
   /  \
  3    3
 / \  / \
1   2 3  4

The answer is 4, because you have a region of 4 connected 3s.

Upvotes: 2

Views: 141

Answers (2)

Dave
Dave

Reputation: 9085

Associate a counter with each node to represent the largest connected region rooted at that node where all the nodes are the same value. Initialize this counter to 1 for every node.

Run DFS on the tree.

When you back up from any node, if both nodes have the same value, add the child node's counter to the parent's counter.

When you're done, the largest counter associated with a node is your answer. You can keep track of this as you run the algorithm.

Upvotes: 0

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

I would suggest a depth first search with a function that takes two inputs:

  1. A target value
  2. A start node

and returns two outputs:

  1. the size of the subtree of node with values equal to the target value
  2. the largest size of connected region within the subtree of node

You can then call this function with a dummy target value (e.g. -1) and the root node and it will return the answer in the second output.

In pseudocode:

dfs(target_value,start_node):
  if start_node.value == target_value:
     total = 1
     best = 0
     for each child of start_node:
       x,m = dfs(target_value,child)
       best = max(m,best)
       total += x
     return total,best
  else
     x,m = dfs(start_node.value,start_node)
     return 0,max(x,m)

_,ans = dfs(-1, root_node)
print ans

Upvotes: 3

Related Questions