Skip to content

Instantly share code, notes, and snippets.

@samoshkin
Created December 2, 2011 11:48
Show Gist options
  • Save samoshkin/1422969 to your computer and use it in GitHub Desktop.
Save samoshkin/1422969 to your computer and use it in GitHub Desktop.
Find common root node for given nodes in a tree
public class TreeAnalyzer
{
public Node FindCommonRoot(IEnumerable<Node> nodes)
{
var walkedNodes = new HashSet<Node>();
var branches = nodes.ToList();
int nextIterationBranchRangeStartIndex = 0;
do
{
for (int i = nextIterationBranchRangeStartIndex; i < branches.Count; i++)
{
nextIterationBranchRangeStartIndex = branches.Count;
var node = branches[i];
if (!walkedNodes.Contains(node))
{
walkedNodes.Add(node);
branches.Add(node.Root);
if(node.Root.Root == null)
{
// root node reached
break;
}
}
}
} while (OnlySingleBranchLeft(branches, nextIterationBranchRangeStartIndex));
return branches[branches.Count - 1];
}
private bool OnlySingleBranchLeft(IList<Node> allBranches, int nextBranchesRangeStartIndex)
{
return allBranches.Count - nextBranchesRangeStartIndex == 1;
}
}
public class Node
{
public Node Root { get { throw new NotImplementedException();} }
public IEnumerable<Node> Children { get { throw new NotImplementedException();} }
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment