Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Approach
3.
Working:
3.1.
Code to find median of BST in C++
3.2.
Time Complexity and Space Complexity
4.
Frequently Asked Questions
4.1.
What is the median of a tree?
4.2.
What is BST?
4.3.
Mention a few applications of BST?
4.4.
What is morris inorder traversal?
4.5.
What is Inorder traversal?
5.
Conclusion
Last Updated: Mar 27, 2024

Find the Median of BST in O(N) Time and O(1) Space

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

We are trying to find out the median of binary search trees(BST) in O(N) time and O(1) space complexity. But before proceeding ahead, what exactly is this median?? Let’s first find this out. 

Also see, Data Structures

The Median is the middle node of a tree, with an almost equal number of nodes in its left and right subparts. It will have nearly an equal number of nodes as a tree can have an even or odd number of total nodes. 

If ‘N’ is the total number of nodes in a tree, then the median will be: (N / 2) + 1 (For an odd number of nodes)

And ((N / 2) + (N / 2 + 1)) / 2 (For even number of nodes)

Recommended: Try the Problem yourself before moving on to the solution.

Approach

To determine the median of BST we need to find out the inorder traversal because inorder traversal will give the binary search tree elements in sorted order. 

 

A simple approach is to use an array to store the inorder traversal of the BST. Storing is required so that we can backtrack to the primary source. But that will take O(N) space which is not allowed. Using the recursive solution for inorder traversal will also use an additional recursive stack that will also take O(N) space. But extra space is not allowed. 

 

An efficient approach is to use morris traversal to figure out the median of BST in O(N) time and O(1) space because it doesn’t take any extra space. For that we first count the total number of nodes in the tree using morris in order traversal that will take O(N) time. After that, we will be traversing once more in the tree, but this time we will be traversing till the count variable becomes equal to the median of the tree. 

 

  • In morris traversal, we initialize three-pointers, ‘curr’ as the current node of the tree, ‘prev’ as the previous node of the tree, and ‘next’ as the next node of the tree. ‘curr’ will be initialized with root.
  • Else find the predecessor of the ‘curr’ pointer. If the right subtree of the ‘curr’ pointer predecessor doesn’t exist, update the current pointer and move to the left subtree. 
  • If the right subtree exists, then update the right predecessor with null. Then visit the current pointer and update the current pointer and move the right subtree.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Working:

To proceed with this question, we must be very clear with the Inorder traversal of a tree. The inorder traversal will give the tree nodes in sorted order; then find out the median of BST. Now, you may be wondering what exactly is this Inorder?? 

 

Animated GIF

Let’s consider a tree; the inorder traversal of the above tree will be :

 

      1       3       4       6       7       8       9

 

Now, as we have figured out our inorder tree traversal, we will find the median of BST. How can we figure out the median using the O(N) time and O(1) space approach? Let’s see. 

For the tree, taken above, come let's find out the median of BST. The inorder traversal of that tree will be :[1, 3, 4, 6, 7, 8, 9]. As it contains odd number of nodes(i.e N = 7), so median will be : (N / 2) + 1

                        = (7 / 2) + 1

                        = 3 + 1

                        = 4

 

And if the tree looks like : 

Binary Tree

 

 

 

This tree has only 6 nodes. So, ((N / 2) + (N / 2 + 1)) / 2

                                                            = ((6 / 2) + (6 / 2 + 1)) / 2

                                                            = ( 3rd node + 4th node ) / 2

                                                            = ( 4 + 6 ) / 2

                                                            = 10 / 2

                                                            = 5

 

Step 1: At first we are using morris traversal to find out the inorder traversal of the tree. For that we are traveling the whole tree once, taking O(N) time. Without visiting the left subtree, figure out the inorder predecessor of the tree. Connect that inorder predecessor to the current node to establish a link between the inorder predecessor and the node, then proceed to the left subtree. Since a connection already exists, we can backtrack to the original node. Links are maintained using pointers. 

Binary Tree

 

 

 

This is the initial tree. For odd median of BST= (N / 2) + 1

                                   For even median of BST = ((N / 2) + (N / 2 + 1)) / 2

 

Step 2: Initially, we will be maintaining three things, ‘curr’ pointer, ‘prev’ pointer, and a counter variable. ‘Curr’ and ‘prev’ will be pointing to NULL, and the counter will be initialized to one. Now, the trick is seen in both the ways for finding median of BST(even and odd), 

(N / 2 + 1) this is common, and we also need an additional term (N / 2). That is just the previous term, that’s why we are maintaining the ‘prev’ pointer also. Now let, K is a variable which holds: K = ( N / 2 ) + 1.

 

Step 3: Run the ‘counter’ till it becomes equal to K. In that position, we already have our required median of BST. We are applying morris traversal one more time; that’s by counting nodes.

Binary Tree

 

 

If prev == NULL, then we will update it with root, and until and unless the counter becomes equal to k, it will keep on incrementing. Here, (1 != 4), counter ++.

 

Step 4: prev will point to the next node, that is prev=3.  

Binary Tree

 

 

 

Step 5: In this step, after incrementing the counter, the counter is now 2, and again 

(2 ! = 4)

 

                                         

Binary Tree


 

 

 

 

Step 6:in this step, the prev pointer is pointing to 4. And the counter is 3, but

 (3 ! = 4), so again keep on incrementing the counter.

 

                                 

Binary Tree

 

 

 

 

Step 7: here, the counter becomes equal to K, the ‘prev’ pointer is still pointing to 4, and the moment when it becomes similar to the counter, update the current with root. Now, outside the loop, if only the median of the BST is asked, for the odd number of nodes, just return the curr,  and for even nodes, return the (curr + prev) / 2.  

 

TrieNode is the BST structure containing three things: data field, two pointers left and right. Insert function inserts the nodes in the BST. First create a ‘treeNode’ type head which is the root node of the BST, initialized with NULL. In the find_median function, three-pointers are created:’curr’, ‘prev’ and ‘pre’, one for current, previous, and one for next. If the current pointer is NULL, for an odd number of nodes, check if the current node is the median, again check for even case, and update the ‘prev’ and ‘curr’ pointers accordingly. Apply morris traversal to find the inorder traversal. Count_nodes function counts the number of nodes in BST.

 

Code to find median of BST in C++

 

#include<bits/stdc++.h>
using namespace std;

/* 
    Created a binary search tree as
    as Node having data, the pointer to left
    and a pointer to the right child a

*/
struct treeNode
{
	int data;
	struct treeNode* left, *right;
};

/* 
    Function to create a new Node
    in BST 
*/
struct treeNode *newNode(int value)
{
	struct treeNode *temp =  new treeNode;
	temp -> data = value;
	temp -> left = temp -> right =  NULL;
	return temp;
}

/* 
    A function to insert a new node with
    given key in BST 
*/
struct treeNode* insert(struct treeNode* node,  int value)
{
	/* 
	    If the tree is empty
	    return the new node with the key
	*/
	if (node ==  NULL)

		      {

		            return newNode(value);

		     
	}

	/* 
	    If the the key is less than particular
	    node data, then call recursion on left
	    else recur on right
	*/
	if (value < node -> data)

		      {
		{	node -> left = insert(node -> left, value);

			     
		}
		else if (value > node -> data)

			     {
			node -> right = insert(node -> right, value);

			     
		}

		/* Return the node */
		return node;
	}

	/*
	    Function to count nodes in a binary search tree
	    using Morris Inorder traversal
	*/
	int countNodes(struct treeNode * head)
	{
		/*
		    Take two pointers current and pre
		    one is the current pointer,  other is
		    previous pointer
		*/
		struct treeNode *current, *previous;

// Initialise count of nodes as 0
		int count =  0;

		if (head ==  NULL)

			      {
			return count;

			     
		}

		current = head;
		while (current !=  NULL)
		{
			if (current -> left ==  NULL)
			{
				/*
				    Count node if its left is NULL
				    and increment count
				*/
				count++;

// Move to its right
				current = current -> right;
			}
			else
			{
				/* 
				    Find the inorder predecessor of current.
				*/
				previous = current -> left;

				while (previous -> right !=  NULL &&
				        previous -> right != current)
					previous = previous -> right;

				/* 
				    Make current as right child of its
				    inorder predecessor 
				*/
				if (previous -> right ==  NULL)
				{
					previous -> right = current;
					current = current -> left;
				}

				/*

				                        Revert the changes made in if part to
				    restore the original tree, the, i.e., fix
				    the right child of the,predecessor

				                   */
				else
				{
					previous -> right =  NULL;

					/* 
					    Increment count if the current
					    node is to be visited
					*/
					count++;
					current = current -> right;
				}



				                   /* 
    If condition ends here as pre->right == NULL 
*/ 
			}



			             /* 
    If the condition ends,
    as current->left==NULL
*/ 
		}

		       /* 
    End of while
*/
		return count;
	}


	/* 
	    Function to find median of BST
	    in O(1) space and O(N) time using
	    morris inorder traversal 
	*/
	int findMedian(struct treeNode * head)
	{

// If root is null, then just return 0
		if (head ==  NULL)

		{
			return 0;

		}

		int count = countNodes(head);
		int currCount =  0;
		struct treeNode *current =  head, *pre, *prev;

		while (current !=  NULL)
		{
			if (current -> left ==  NULL)
			{
// Count current node
				currCount++;

				/* 
				    For odd cases check if current
				    node is the median
				*/
				if (count %  2 !=  0 && currCount == (count +  1) /  2)

					                    {
					return prev->data;

					                   
				}

// Even case
				else if (count %  2 ==  0 && currCount == (count /  2) +  1)

					                    {
					return (prev -> data + current -> data) /  2;

					                   
				}

// Update prev for even no. of nodes
				prev = current;

// Move to the right
				current = current->right;
			}
			else
			{
				/* 
				    Find the inorder predecessor
				    of current 
				      */
				pre = current->left;
				while (pre -> right !=  NULL && pre -> right != current)
					pre = pre->right;

				/* 
				      Make current as the right child 
				      of its inorder predecessor 
				*/
				if (pre -> right ==  NULL)
				{
					pre -> right = current;
					current = current -> left;
				}

				/* 
				    Reverse the changes made
				    in if part of restoring the 
				    original tree,handy for i.e., fix the
				    right child of predecessor 
				*/
				else
				{
					pre->right =  NULL;

					prev = pre;

// Count current node
					currCount++;

// Check if the current node is the median
					if (count %  2 !=  0 && currCount == (count +  1) /  2 )

						                          {
						return current->data;

						                         
					}

					else if (count %  2  ==  0 && currCount == (count / 2) + 1)

						                        {
						return (prev->data + current->data) /  2;

						                          
					}


					/*
					    For even case, Update
					    the current node
					*/
					prev = current;
					current = current->right;
				}

				                    /* 
    If condition ends
    pre->right == NULL 
*/ 
			}

			             /* 
    The restoring of condition ends as
    current->left == NULL
*/ 
		}

		       /* 
    End of while loop
*/
	}

// main Function
	int main()
	{
		/*

		          Let us create the following BST
		  6
		  / \
		3   8
		/ \ / \
		      1 4 7  9 
		*/

		/*
		    Inserting the values
		    for creating tree
		*/
		struct treeNode *head =  NULL;
		head = insert(head,  6);
		insert(head,  3);
		insert(head,  8);
		insert(head,  1);
		insert(head,  4);
		insert(head,  7);
		insert(head,  9);

		/*
		    Printing the ans
		    of median of BST in O(N)
		    time and O(1) space
		*/
		cout <<  "\n Median of BST is:"
		     << findMedian(head);
		return 0;
	}

 

Output :

Median of BST is: 6

Time Complexity and Space Complexity

 

Time: O(N)

Space: O(1)

The time complexity for this problem is O(N) as we are traversing the whole tree once initially using morris traversal for counting the total number of nodes. Space complexity is O(1) only, as no extra space is being used.

Frequently Asked Questions

What is the median of a tree?

Median is the middle node of a tree, with an almost equal number of nodes in its left and right subparts.
If number of nodes is odd, median = (N / 2) + 1
If N is odd, median = ((N / 2) + (N / 2 + 1)) / 2.

What is BST?

A BST is a tree that has at most two child nodes. The value in the left subtree of a node in a  BST is smaller than that node and the value in the right subtree of a node is greater than that node. Each left and right subtree is itself a BST in it.

Mention a few applications of BST?

Binary search tree (BST) has many applications listed below:
They are handy for multilevel indexing.
They can be used for implementing various sorting applications.
BST is beneficial for handling sorted data values.

What is morris inorder traversal?

In morris traversal, we traverse the tree without using recursion and stack. Instead, we first create links to the Inorder successor and then print them using these links. Later, we backtrack to the original tree.

What is Inorder traversal?

Inorder traversal gives the tree nodes in sorted order. All tree nodes are processed recursively, beginning with the left subtree, moving towards the root, and ending with the right subtree.
 

Conclusion

This article taught us to find the median of BST using O(N) time and O(1) space using morris traversal and its implementation in the C++ programming language. 

Now, we recommend you practice problem sets based on these concepts to master your skills. You can get a wide range of questions similar to the median of BST to more exciting BST problems in Code Studio

Recommended Reading:

Keep learning and keep coding.

Previous article
Queuing Problem
Next article
Kth Largest Element BST
Live masterclass