为何二叉搜索树Kth最小节点查找的原中序函数触发段错误？

给定一棵二叉搜索树，任务是找到树中第K小节点的子树的中位数。每个测试用例单独一行输出该中位数。
约束条件：

• 1 ≤ T ≤ 30
• 1 ≤ 节点数 ≤ 100
• 1 ≤ 节点数据 ≤ 1000
• 1 ≤ K ≤ 节点数

示例输入：

1
12 9
50 25 75 15 45 90 11 20 30 49 80 100

示例输出：85

我针对该问题编写了解决方案，原inorder函数如下：

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);
    }
    
}

本地编译运行能得到正确结果，但提交至GFG时出现段错误。将inorder函数修改为以下版本后，其余代码不变，提交则正常运行：

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;
}

请问为何原inorder函数会引发段错误，修改后则正常？

原因分析 #

原函数的核心问题是非void类型函数存在无返回值的路径，这属于C++未定义行为：

• 当root不为空时，若左子树遍历没找到目标节点，且当前节点也不是第K小节点，遍历完右子树后函数没有返回语句，此时会返回栈上的随机垃圾地址。
• 当root为空时，原函数同样没有返回值，返回的随机数据会被调用者当作有效指针处理，直接导致内存访问错误（段错误）。

修改后的函数彻底解决了这个问题：

• 所有分支都明确设置了返回值：左子树找到结果直接返回，当前节点是目标则返回，右子树找到结果也返回；空节点或未找到时返回NULL。
• 调用者拿到的要么是有效节点指针，要么是NULL，不会出现访问非法内存的情况，自然避免了段错误。

内容的提问来源于stack exchange，提问作者user15998452