finding second smallest element in binary search tree

Question

int secondSmallestInBST(struct node * tNode) {
if( tNode==NULL || (tNode->left==NULL && tNode->right==NULL) )  // case 1 and 2
    exit;
if(tNode->left == NULL){                     // case 3
    tNode=tNode->right;
    while(tNode->left!=NULL){
        tNode=tNode->left;
    }
    return tNode->data;
}                                                     // general case.
node * parent=tNode,* child = tNode->left;
while(child->left!=NULL){
    parent = child;
    child = child->left;
}
return parent->data;

}

not every test cases are passed for my code. suggest me if there is any test case missing in my code. i'm just finding the second smallest element in binary search tree.

int secondSmallestInBST(struct node * tNode) {
if( tNode==NULL || (tNode->left==NULL && tNode->right==NULL) )  // case 1 and 2
    exit;
if(tNode->left == NULL){                     // case 3
    tNode=tNode->right;                     // find smallest in right bst.
    while(tNode->left!=NULL){
        tNode=tNode->left;
    }
    return tNode->data;
}                                                     // general case.
if(tNode->left->left==NULL && tNode->left->right!=NULL){   //missed case.
    tNode=tNode->left->right;
    while(tNode->left!=NULL){
        tNode=tNode->left;
    }
    return tNode->data;
}
node * parent= tNode;
node * child = tNode->left;
while(child->left!=NULL){
    parent = child;
    child = child->left;
}
return parent->data;

}

//still missing some test cases in this code.

please, add programming language as tag and, if you can, provide an example of failing test — MrPk
– MrPk, Commented Feb 13, 2017 at 9:30
@MrPk i'm asking if i'm forgetting some test case in my code. — Sahil Kumar
– Sahil Kumar, Commented Feb 13, 2017 at 9:45

Manisha · Accepted Answer · 2017-02-09 09:05:19Z

1

Test for this case - 3 6 2 3. Tree will look like this :

The way you are doing, answer will come out to be 6, whereas it is 3.

answered Feb 9, 2017 at 9:05

Manisha

1364 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Sahil Kumar Over a year ago

i have added your test case to my code even though it is partially accepted.

Eldar · Accepted Answer · 2018-03-04 17:53:35Z

`

int Successor(Node* root){
  while(root->left){
    root = root->left;
  }
  return root->data;
}

int Second_Minimum(Node* root){
  //  make sure tree is not empty
  if(!root)
    return -1;
  // previous node takes before the last left node
  Node* previous = root;
  // check left node first for smallest key
  if(root->left){
    while(root->left){
      previous = root;
      root = root->left;        //    6
    }                           //   /
    // checks for the case ---->    2
    if(!root->right)            //   \
      return previous->data;    //    3 
  }
  // Go for minimum successor if exists 
  if(root->right)
    return Successor(root->right);
  // checked left and right branch root is on his own 
  return -1;
}

`

HojjatK · Accepted Answer · 2019-06-16 10:20:33Z

A BST inorder traverse gives elements in order (sorted). So the idea is to return the second element in the traverse(if tree has less than two elements then it won't have second minimum and should return null (not found)).

The following code implements the algorithm. Note that the algorithm can be changed to return the K'th minimum element as well easily.

Code has been written in C# (easily can be written in other languages:-) enjoy!

public static int? FindSecondMimimum(Node node)
{
    int current = 0;
    return FindKthMinimum(node, 2, ref current);
}

private static int? FindKthMinimum(Node node, int k, ref int current)
{
    int? result = null;
    if (node == null)
        return null;

    if (node.Left != null)
    {
        result = FindKthMinimum(node.Left, k, ref current);
        if (result != null)
            return result;
    }

    current++;
    if (current == k)
        return node.Value;

    if (node.Right != null)
    {
        result = FindKthMinimum(node.Right, k, ref current);
    }

    return result;
}

Collectives™ on Stack Overflow

finding second smallest element in binary search tree

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related