Thursday, 30 November 2017

Kth smallest element in a BST - C++ Code


Do inorder Traversal of BST and count number of elements traversed till now . As inorder traversal gives us the element in sorted Order, when count reaches k , we break out and Print the element.


/**
 * Definition for Binary Search Tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 * };
 */
int kthsmallest(TreeNode* root, int k) {
    if(root==NULL)
      return 0;
    stack<TreeNode*> s;
    bool complete=false;
    TreeNode* cur=root;
    int count=0;
    int val=0;
    while(!complete)
    {
        if(cur!=NULL)
        {
            s.push(cur);
            cur=cur->left;
        }
        else
        {
            if(!s.empty())
            {
                count++;
                cur=s.top();
                s.pop();
                if(count==k)
                {
                    val=cur->val;       
      break;
                }
                  cur=cur->right;
            }
            else
              complete=true;
        }  
    }
    return val;
}


Please comment if you find anything incorrect.

Monday, 6 November 2017

First Non Repeating Character in String


#include<iostream>
#include<string>
#include<memory>
#include<climits>
#define NUMBER_OF_CHARS 256
using namespace std;
struct CountIndex
{

 int count;
 int index;
};
char getFirstNonRepeatngCharacter(const string& str)
{
 char ch=' ';
 unique_ptr<CountIndex[]> ci(new CountIndex[256]());
 //Can also use shared_ptr
 //shared_ptr<CountIndex> ci(new CountIndex[256](),std::default_delete<CountIndex[]>());
 for(auto& it:str)
 {
  ci.get()[it].count++;
  if(ci.get()[it].count==1)
   ci.get()[it].index= &it - &str[0];
  else

   ci.get()[it].index= ci.get()[it].index;

 }
 int maxIndex=INT_MAX;

 for(int it=0;it<NUMBER_OF_CHARS;it++)
 {
  if(ci.get()[it].count==1 && ci.get()[it].index <maxIndex)
  {
   maxIndex= ci.get()[it].index;

  }
 }
 return maxIndex!=INT_MAX?str[maxIndex]:' ';
}
int main()
{    
 string str ;
 cin>>str;
 char ch=getFirstNonRepeatngCharacter(str);
 if(ch !=' ')
  cout<<" First Non repeating Character is "<< ch;
 else
  cout<<" No Repeating Character Exist ";


}