Question
Median of a BST
You are given the root of a Binary Search Tree (BST). Your task is to find the median of the tree.
Note: The number of nodes in the BST is guaranteed to be odd.
Note: The number of nodes in the BST is guaranteed to be odd.
Input
User Task
Since this is a functional problem, you do not need to handle input or output. Your task is to complete the function medianOfBST(), which takes the root node as its parameters.
Custom Input
The first line of input contains space separated integers, N, representing the number of nodes in the tree.
The next line consists of space-separated integers denoting the level order traversal of the tree, where non-negative values represent node values, and -1 indicates a null node.
Note: Once a node is marked as -1, no further information about its children is provided.
Since this is a functional problem, you do not need to handle input or output. Your task is to complete the function medianOfBST(), which takes the root node as its parameters.
Custom Input
The first line of input contains space separated integers, N, representing the number of nodes in the tree.
The next line consists of space-separated integers denoting the level order traversal of the tree, where non-negative values represent node values, and -1 indicates a null node.
Note: Once a node is marked as -1, no further information about its children is provided.
Output
Return the median of the Binary Search Tree
Example
Input
9
7 2 15 1 5 12 20 -1 -1 3 -1 10
Output
7
Explanation
The nodes of this BST in the sorted order are [1,2,3,5,7,10,12,15,20]. In this, the median node is 7.
9
7 2 15 1 5 12 20 -1 -1 3 -1 10
Output
7
Explanation
The nodes of this BST in the sorted order are [1,2,3,5,7,10,12,15,20]. In this, the median node is 7.