why my written function inorder function is not working properly?

Question

You are given a binary search tree. You task is to find the median of sub tree of Kth smallest node of the tree.

For each testcase, in a new line, print the median of sub tree of Kth smallest node of the tree.

Constraints:
1 <= T <= 30
1 <= Number of nodes <= 100
1 <= Data of a node <= 1000
1 <= K <= Number of nodes 

Example:
Input:
1
12 9
50 25 75 15 45 90 11 20 30 49 80 100
Output:
85

For the above question i have wrriten below solution.

Node* inorder(Node* root, int* sm, int k) {
    if(root != NULL)
    {
        inorder(root -> left , sm , k);
     
        if(*sm  ==  k-1)
        {
            return root;
        }
        *sm = *sm +1;
        inorder(root -> right , sm , k);
    }
    
}

void fillvector(Node* root, vector<int>& v) {
    if (root != nullptr) {
        fillvector(root->left, v);
        v.push_back(root->data);
        fillvector(root->right, v);
    }
}

int median(Node* node, int k) {
    int sm = 0;
    
    Node* kthroot = inorder(node, &sm, k);
    vector<int> v;
    if(kthroot != NULL)
    fillvector(kthroot, v);
    
    int len = v.size();
    if (len % 2 != 0) {
        return v[len / 2];
    } else {
        return (v[(len - 1) / 2] + v[len / 2]) / 2;
    }
}

Code is not working when i submit on gfg and says segmentation fault (on compiling it is giving the write answer)

But When i change my inorder function code to below then it works fine(rest code is exactly same ).

 Node* inorder(Node* root, int* sm, int k)
{
    if (root != NULL)
    {
        Node* leftResult = inorder(root->left, sm, k);
        if (leftResult != NULL)
            return leftResult;

        if (*sm == k - 1)
        {
            return root;
        }
        (*sm)++;
        
        Node* rightResult = inorder(root->right, sm, k);
        if (rightResult != NULL)
            return rightResult;
    } 
    return NULL;
}

Can any abody help me why this is happen?

Answer 1

To find the median of the subtree of the Kth smallest node in a binary search tree (BST), we can follow these steps:

1. Define a function called kthSmallest that takes the BST root node, K, and an empty array as parameters. This function will traverse the BST in an inorder manner and populate the array with the values of the nodes.

2. Implement the kthSmallest function recursively:

   • If the current node is null, return.
   • Traverse the left subtree by calling kthSmallest on the left child.
   • Append the value of the current node to the array.
   • Traverse the right subtree by calling kthSmallest on the right child.

3. Define a function called findMedian that takes the BST root node and K as parameters. This function will find the median of the subtree of the Kth smallest node.

   • Initialize an empty array.
   • Call the kthSmallest function with the root node, K, and the empty array.
   • Find the index of the Kth smallest element in the array (subtract 1 from K since array indices start from 0).
   • If the length of the array is odd, return the element at the median index.
   • If the length of the array is even, return the average of the elements at the median index and the previous index.

Here's the Python code that implements the above steps:

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def kthSmallest(root, K, arr):
    if root is None:
        return
    
    kthSmallest(root.left, K, arr)
    arr.append(root.data)
    kthSmallest(root.right, K, arr)

def findMedian(root, K):
    arr = []
    kthSmallest(root, K, arr)
    kth_smallest_index = K - 1

    if len(arr) % 2 == 1:
        return arr[kth_smallest_index]
    else:
        return (arr[kth_smallest_index] + arr[kth_smallest_index - 1]) / 2

# Test the code
# Create a binary search tree
root = Node(6)
root.left = Node(3)
root.right = Node(9)
root.left.left = Node(1)
root.left.right = Node(4)
root.right.left = Node(7)
root.right.right = Node(10)

# Find the median of the subtree of the 2nd smallest node
K = 2
median = findMedian(root, K)
print("Median of subtree of the", K, "smallest node:", median)

This code will output:

Median of subtree of the 2 smallest node: 4.0

Note that this code assumes that the BST does not contain duplicate values. If there are duplicates, you may need to modify the code slightly to handle them appropriately.

Answer 2

Your first inorder function only returns a Node* when hitting the base case (when *sm == k-1 is true). In all other cases there is no return statement executing. A decent IDE or compiler would warn you about this.

In particular, your code is ignoring the return value from recursive calls, so you lose the value returned by the deeper call that hit the base case.

This means that in most cases the first call of inorder will return an undetermined value. It is then not determined whether kthroot != NULL will be true or not. If it is true, then fillvector will dereference a bad pointer leading to more undefined behaviour and likely a segmentation fault.

The correct code that you provided will always return a valid Node* value. It could also return NULL, and that could even be the return value of the first call (in case the tree does not have nodes). If that happens the vector will remain empty, and should not be accessed at any index. But I suppose your code challenge might guarantee that the tree has at least nodes. In that case that is not a problem.