145. Path to deepest 1 in a binary tree.......
Microsoft Interview Questions and Answers
(Continued from previous question...)
145. Path to deepest 1 in a binary tree.......
Question:
Path to deepest 1 in a binary tree.
We have a binary tree (not a BST) made up of only 0s and 1s. we need to find the deepest 1 with a path from root made up only of 1's.
maybe an answer:
It is easy to solve this if the path is not required. But if path is required it becomes little more complex.
public List<BinaryNode> FindPathToDeepest1Node(BinaryNode startNode)
{
if (null == startNode)
{
return null;
}
List<BinaryNode> deepest1Path = new List();
int pathLen = FindPathToDeepest1NodeRecur(startNode, ref deepest1Path);
Console.WriteLine("Path length of the longest path with 1's is {0}", pathLen);
return deepest1Path;
}
private int FindPathToDeepest1NodeRecur(BinaryNode startNode, ref List<BinaryNode> deepest1Path)
{
int pathLen = 0;
if (null == startNode || startNode.Value == BinValue.Zero)
{
return pathLen;
}
deepest1Path.Add(startNode);
pathLen++;
List<BinaryNode> deepest1PathLeft = new List<BinaryNode>();
int deepestLenInLeftSubTree = FindPathToDeepest1NodeRecur(startNode.Left, ref deepest1PathLeft);
List<BinaryNode> deepest1PathRight = new List<BinaryNode>();
int deepestLenInRightSubTree = FindPathToDeepest1NodeRecur(startNode.Right, ref deepest1PathRight);
if (deepestLenInLeftSubTree >= deepestLenInRightSubTree)
{
deepest1Path.AddRange(deepest1PathLeft);
pathLen += deepestLenInLeftSubTree;
}
else
{
deepest1Path.AddRange(deepest1PathRight);
pathLen += deepestLenInRightSubTree;
}
return pathLen;
}
(Continued on next question...)
Other Interview Questions
|