CareerCup

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

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.

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

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.

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?

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.

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

hihjhji