This content originally appeared on DEV Community and was authored by Manasi Patil
Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀
100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney
Problem:
https://www.geeksforgeeks.org/problems/bst-to-greater-sum-tree/1
Median of BST
Difficulty: Medium Accuracy: 27.43%
You are given the root of a Binary Search Tree, find the median of it.
Let the nodes of the BST, when written in ascending order (inorder traversal), be represented as V1, V2, V3, …, Vn, where n is the total number of nodes in the BST.
• If number of nodes are even: return V(n/2)
• If number of nodes are odd: return V((n+1)/2)
Examples:
Input: root = [20, 8, 22, 4, 12, N, N, N, N, 10, 14]
Output: 12
Explanation: The inorder of given BST is 4, 8, 10, 12, 14, 20, 22. Here, n = 7, so, here median will be ((7+1)/2)th value, i.e., 4th value, i.e, 12.
Input: root = [5, 4, 8, 1]
Output: 4
Explanation: The inorder of given BST is 1, 4, 5, 8. Here, n = 4(even), so, here median will be (4/2)th value, i.e., 2nd value, i.e, 4.
Constraints:
1 ≤ number of nodes ≤ 105
1 ≤ node.data ≤ 105
Solution:
class Solution:
def findMedian(self, root):
def inorder(node):
if not node:
return []
return inorder(node.left) + [node.data] + inorder(node.right)
vals = inorder(root)
n = len(vals)
if n % 2 == 1:
return vals[n // 2]
else:
return vals[(n // 2) - 1]
This content originally appeared on DEV Community and was authored by Manasi Patil
Manasi Patil | Sciencx (2025-10-18T04:35:09+00:00) Day 17 of 100 days dsa coding challenge. Retrieved from https://www.scien.cx/2025/10/18/day-17-of-100-days-dsa-coding-challenge/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.