C# mock interview practice with optimal time complexity
July 14, 2020
865. Smallest Subtree with all the Deepest Nodes
Introduction
It is the second algorithm in my mock interview today. It took me less than 30 minutes to come out the idea and write the solution. Also the solution is designed with optimal time complexity O(N), N is total nof nodes in the tree, and space complexity is O(1).
Case study
I asked myself to work on a simple solution, and make it work first.
The test case is a binary tree like root 1, left 2, right 3, and right.right = 4.
I like to apply post order traversal, so that each recursive function will return three things, first is longest path from root to leaf node, second one is the TreeNode which is candidate for the deepest node, third one is to track it's longest path to leaf node.
Time complexity
O(N), N is total number of nodes in the tree.
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
public TreeNode SubtreeWithAllDeepest(TreeNode root) {
// the idea is to apply post order traversal
// if there are two children, both have same depth - return root
// if one is bigger, than go to the bigger
// recursive function is design to return depth from root to leaf node maximum path
var result = runPostOrderTraversal(root);
return result.Item2;
}
/// root 1, left 2, right 3, and right.right = 4
private Tuple<int, TreeNode, int> runPostOrderTraversal(TreeNode root)
{
if(root == null)
{
return new Tuple<int, TreeNode, int>(0, null, 0);
}
// Left, right
var left = runPostOrderTraversal(root.left); // 2
var right = runPostOrderTraversal(root.right);
var path1 = left.Item1;
var path2 = right.Item1;
if(path1 == path2)
{
return new Tuple<int, TreeNode, int>(path1 + 1, root, path1 + 1);
}
else if(path1 < path2)
{
return new Tuple<int, TreeNode, int>(path2 + 1, right.Item2, right.Item3);
}
else
return new Tuple<int, TreeNode, int>(path1 + 1, left.Item2, left.Item3);
}
}
