CODEWITHSUNDEEP
algorithmdata-structurestreetree-traversal
Dänu
Dänu

Reputation: 5929

An algorithm which finds a path in a tree along the maximum node values at each level

I am looking for an algorithm which finds a path in a tree along the maximum node values at each level. The following graphic illustrates the problem:

tree

If all nodes on a level would have unique values, this problem would be quite trivial. However, if there are duplicate values on a level, then I (assume that I) need some sort of look ahead. As shown in the example, if there is a draw, the path is chosen which allows for a higher value in the next level. Taken to an "extreme", the path

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 0

would be chosen over the path

1 -> 2 -> 3 -> 4 -> 5 -> 5 -> 99

As soon as there is only one possible path, the algorithm may exit.

Until now, my naive solution has been to find all the possible paths and them compare them level by level, which works for the (small) trees I am dealing with, but I'd like to find a "proper" solution.

I am quite sure that this algorithm has already been implemented, however, I find it hard to find the right search terms for it. Is anyone aware of a solution to this problem?

Upvotes: 2

Views: 71

Answers (2)

Graffito
Graffito

Reputation: 1718

Here is a possible implementation (not tested)

Assume a tree structure based on Nodes as follow:

internal class Node
{
  int Value ;
  List<Node> Children ;
}

Main program

// Initialize the best path and call the Seek procedure
List<Node> BestPath = SeekBestSubPath(TheRootNode)

Recursive function

private List<Node> SeekBestSubPath(Node CurrentNode)
{
  // identify one or more children with max value   
  List<Node> BestChildrenNodes = null ;
  int Max = int.MinValue ;
  for (int i=0;i<CurrentNode.Children.Count;i++)
    if (CurrentNode.Children[i].Value > Max) 
      BestChildrenNodes=new List<Node>() { CurrentNode.Children[i] } ;
    else if (CurrentNode.Children[i].Value == Max)
      BestChildrenNodes.Add(CurrentNode.Children[i]) ;

  // Process BestChildrenNodes
  List<Nodes> result = new List<Node>() ;
  for (int i=0;i<BestChildrenNodes.Count;i++)
  { // search the best sub path for each child and keep the best one among all  
    List<Node> ChildBestSubPath = SeekBestSubPath(BestChildrenNodes[i]) ;
    if (PathComparator(ChildBestSubPath,MaxPath)>1) result=ChildBestSubPath ;
  }
  result.Insert(0,CurrentNode) ;
  return result ;
}

Compare 2 subpaths

private PathComparator(List<Node> Path1,List<Node> Path2)
{ returns 0:equality, 1:Path1>Path2, -1:Path1<Path2
  int result = 0
  for (int i=0;i<Math.Min(Path1.Length,Path2.length) && result=0;i++)
     result=Math.Sign((Path1[i].Value).CompareTo(Path2[i].Value));
  if (result==0) result=Math.Sign(((Path1[i].Count).CompareTo(Path2[i].Count)); 
  return result ;
}

Upvotes: 1

kraskevich
kraskevich

Reputation: 18546

You can start from the root and maintain the list of candidates. Initially the root is the only element in the list. At each iteration you can look at all children of the current candidates and put those that have the maximum value into a new candidates list (that is, each iteration goes one level lower).

Each node is visited at most once, so this solution has a linear time complexity.

Upvotes: 1

Related Questions