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) + 1If N is odd, median = ((N / 2) + (N / 2 + 1)) / 2.

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.

Find the median of BST in O(N) time and O(1) space.

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.

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)

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 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.

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??

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.

Source: Giphy

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 :

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.

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++:

#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.

Key takeaways:

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.