## Google Interview Question for Software Engineers

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 vote

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Perform an inorder traversal and then look at the middle element.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Find total node count, then do an inorder traversal of the bst and have an index which increments for each node visited. If total node count was even then stop when you reach idx = n/2, otherwise stop at (n-1)/2.

Comment hidden because of low score. Click to expand.
0
of 0 vote

If it is a balanced bst, I think you could simply return the root or the one right before or after it. What do you think?

Comment hidden because of low score. Click to expand.
0
of 0 vote

We can do an inorder traversal twice, first to find the count. Second to get the median based on that count using an array with single element.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

hihjhji

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.