Google Interview Question
Software EngineersCountry: India
Interview Type: In-Person
Step 1 is the count of the number of nodes in the BST.
public static int GetNodeCountBST(Node root)
{
if(root == null)
{
return 0;
}
Node currentNode = root;
return GetNodeCountBSTRec(currentNode);
}
private static int GetNodeCountBST(Node node)
{
if(node == null)
{
return 0;
}
return GetNodeCountBST(node.left) + 1 + GetNodeCountBST(node.right);
}
Step 2 is to find the median
public static double? FindMedian(Node root, int nodeCount)
{
if(root == null || nodeCount <= 0)
{
return null;
}
Int median= 0;
Node currentNode = root;
FindMedianRec(currentNode, nodeCount, 0, out median);
return median;
}
private static int FindMedianRec(Node node, int totalCount, int nodeCount, out double median)
{
if(node == null)
{
return nodeCount;
}
int leftNodeCount = FindMedianRec(node.left, totalCount, nodeCount, out median);
if(leftNodeCount == (TotalCount-1)/2)
{
median = node.data;
}
if(leftNodeCount == (TotalCount/2))
{
if(TotalCount % 2 == 0)
{
median = (median + (double)node.data)/2;
}
}
return FindMedianRec(node.right, totalCount, nodeCount + 1 + leftNodeCount, out median);
}
Complexity of both the steps is O(N) and space complexity is O(1) only.
public static float findMedianOfTree(TreeNode root){
int count = findnumOfNodes(root);
if(count == 1){
return root.val;
}
if(count%2==1){
return findkthEleTree(root,count/2+1);
}else{
return (findkthEleTree(root,count/2)+findkthEleTree(root,count/2+1))/(float)2;
}
}
public static int findkthEleTree(TreeNode root,int k){
int left_count = findnumOfNodes(root.left);
if(left_count+1==k){
return root.val;
}else if(left_count+1<k){
return findkthEleTree(root.right,k-left_count-1);
}else{
return findkthEleTree(root.left,k);
}
}
public static int findnumOfNodes(TreeNode root){
if(root==null) return 0;
return findnumOfNodes(root.left)+1+findnumOfNodes(root.right);
}
The solution is Morris Traversal i.e to do the inorder traversal without extra space, We just need to do inorder traversal using morris traversal till we find the median which can be n/2 for even count and (n-1)/2 when count is odd
- jerry April 18, 2017