Interview Questions

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