Find Median in BST Subtree from Kth Smallest Node
Given a binary search tree, the task is to find the median of the subtree rooted with Kth smallest node of the tree.
Examples:
Input: N = 12, K = 9
50
/ \
25 75
/ \ \
15 45 90
/ \ / \ / \
11 20 30 49 80 100Output: 85
Explanation: K=9. So the 9th smallest number is 75. The values of this subtree are 75 80 90 100. Now, the median of this is (80+90)/2 = 85
Approach: This can be solved with the following idea:
As it is BST, Inorder traversal of tree will give us sorted array. From there we can get the Kth smallest node. After that, iterate for that particular node and get the median.
Below are the steps involved:
- Intialize a nodes of vector v.
- Traverse in inorder, So as to get sorted vector.
- Get the Kth smallest node.
- Again Iterate in inorder traversal for kth samllest node and store them in another vector.
- Once done, check the size of vector:
- If even, median will be sum of both mid divide by 2.
- If odd, median will be mid of vector.
Below is the implementation of the code:
C++
// Initial Template for C++ #include <bits/stdc++.h> using namespace std; // Creating a node structure struct Node { int data; Node* left; Node* right; }; // Function to create a new node Node* newNode( int data) { Node* temp = new Node; temp->data = data; temp->left = temp->right = NULL; return temp; } // Function to insert a new node in BST Node* insert(Node* root, int data) { if (root == NULL) root = newNode(data); else if (data < root->data) root->left = insert(root->left, data); else root->right = insert(root->right, data); return root; } // Function to iterate in inorder behaviour void inorder(vector<Node*>& v, Node* root) { if (root == NULL) { return ; } inorder(v, root->left); v.push_back(root); inorder(v, root->right); return ; } // Function to find median for Kth smallest node in BST int median(Node* node, int k) { // Intialization of vector of nodes vector<Node*> v; inorder(v, node); vector<Node*> v1; // Forming a vector for kth smallest node inorder(v1, v[k - 1]); // If size is even if (v1.size() % 2 == 0) { int mid = v1.size() / 2; return (v1[mid]->data + v1[mid - 1]->data) / 2; } return v1[v1.size() / 2]->data; return 0; } // Driver code int main() { Node* root = NULL; int n = 4; int k = 2; vector< int > nodes = { 3, 2, 4, 1 }; for ( int i = 0; i < n; i++) { int x = nodes[i]; root = insert(root, x); } // Function call cout << median(root, k) << endl; return 0; } |
Java
/*code by Flutterfly*/ import java.util.ArrayList; import java.util.List; // Creating a node structure class Node { int data; Node left, right; Node( int data) { this .data = data; left = right = null ; } } public class Main { // Function to insert a new node in BST static Node insert(Node root, int data) { if (root == null ) return new Node(data); else if (data < root.data) root.left = insert(root.left, data); else root.right = insert(root.right, data); return root; } // Function to iterate in inorder behavior static void inorder(List<Node> v, Node root) { if (root == null ) { return ; } inorder(v, root.left); v.add(root); inorder(v, root.right); } // Function to find median for Kth smallest node in BST static int median(Node node, int k) { List<Node> v = new ArrayList<>(); inorder(v, node); List<Node> v1 = new ArrayList<>(); inorder(v1, v.get(k - 1 )); // If size is even if (v1.size() % 2 == 0 ) { int mid = v1.size() / 2 ; return (v1.get(mid).data + v1.get(mid - 1 ).data) / 2 ; } return v1.get(v1.size() / 2 ).data; } // Driver code public static void main(String[] args) { Node root = null ; int n = 4 ; int k = 2 ; int [] nodes = { 3 , 2 , 4 , 1 }; for ( int i = 0 ; i < n; i++) { int x = nodes[i]; root = insert(root, x); } // Function call System.out.println(median(root, k)); } } |
Python3
# Creating a node class class Node: def __init__( self , data): self .data = data self .left = None self .right = None # Function to insert a new node in BST def insert(root, data): if root is None : return Node(data) elif data < root.data: root.left = insert(root.left, data) else : root.right = insert(root.right, data) return root # Function to iterate in inorder behavior def inorder(v, root): if root is None : return inorder(v, root.left) v.append(root) inorder(v, root.right) # Function to find median for Kth smallest node in BST def median(node, k): # Initialization of a list of nodes v = [] inorder(v, node) v1 = [] # Forming a list for kth smallest node inorder(v1, v[k - 1 ]) # If the size is even if len (v1) % 2 = = 0 : mid = len (v1) / / 2 return (v1[mid].data + v1[mid - 1 ].data) / / 2 return v1[ len (v1) / / 2 ].data # Driver code if __name__ = = "__main__" : root = None n = 4 k = 2 nodes = [ 3 , 2 , 4 , 1 ] for x in nodes: root = insert(root, x) # Function call print (median(root, k)) |
C#
// code by Flutterfly using System; using System.Collections.Generic; // Creating a node structure public class Node { public int data; public Node left, right; public Node( int data) { this .data = data; left = right = null ; } } public class Program { // Function to insert a new node in BST static Node Insert(Node root, int data) { if (root == null ) return new Node(data); else if (data < root.data) root.left = Insert(root.left, data); else root.right = Insert(root.right, data); return root; } // Function to iterate in inorder behavior static void Inorder(List<Node> v, Node root) { if (root == null ) { return ; } Inorder(v, root.left); v.Add(root); Inorder(v, root.right); } // Function to find median for Kth smallest node in BST static int Median(Node node, int k) { List<Node> v = new List<Node>(); Inorder(v, node); List<Node> v1 = new List<Node>(); Inorder(v1, v[k - 1]); // If size is even if (v1.Count % 2 == 0) { int mid = v1.Count / 2; return (v1[mid].data + v1[mid - 1].data) / 2; } return v1[v1.Count / 2].data; } // Driver code public static void Main() { Node root = null ; int n = 4; int k = 2; int [] nodes = { 3, 2, 4, 1 }; for ( int i = 0; i < n; i++) { int x = nodes[i]; root = Insert(root, x); } // Function call Console.WriteLine(Median(root, k)); } } |
Javascript
// Creating a node structure class Node { constructor(data) { this .data = data; this .left = null ; this .right = null ; } } // Function to insert a new node in BST function insert(root, data) { if (root === null ) return new Node(data); else if (data < root.data) root.left = insert(root.left, data); else root.right = insert(root.right, data); return root; } // Function to iterate in inorder behavior function inorder(v, root) { if (root === null ) { return ; } inorder(v, root.left); v.push(root); inorder(v, root.right); } // Function to find median for Kth smallest node in BST function median(node, k) { const v = []; inorder(v, node); const v1 = []; inorder(v1, v[k - 1]); // If size is even if (v1.length % 2 === 0) { const mid = v1.length / 2; return Math.floor((v1[mid].data + v1[mid - 1].data) / 2); } return v1[Math.floor(v1.length / 2)].data; } // Driver code let root = null ; const n = 4; const k = 2; const nodes = [3, 2, 4, 1]; for (let i = 0; i < n; i++) { const x = nodes[i]; root = insert(root, x); } // Function call console.log(median(root, k)); |
1
Time Complexity: O(N)
Auxiliary Space: O(N)