Find the median of BST in O(N) time and O(1) space.
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.
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)
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 inorder 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.
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??
Let’s consider a tree; the inorder traversal of the above tree will be :
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
And if the tree looks like :
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
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.
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.
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.
Step 5: In this step, after incrementing the counter, the counter is now 2, and again
(2 ! = 4)
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.
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++:
Revert the changes made in if part to
Let us create the following BST
|Median of BST is: 6|
Time Complexity and Space Complexity :
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.
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.
Keep learning and keep coding.