Verify if a given tree T1 a subtree of a binary tree T2

bool checkForSubtree(node *head, node *subHead){
bool l,r;
if(subHead){
if(head->data == subHead->data){
if(subHead->left){
l = checkForSubtree(head->left, subHead->left);
}else l = true;
if(subHead->right){
r = checkForSubtree(head->right, subHead->right);
}else r = true;
if(l&&r)return true;
else return false;
}else{
return false;
}
}
}

bool checkSubtree(node *head, node *subHead){
bool left = false, right=false;
if(head){
if(head->data == subHead->data){
if(checkForSubtree(head, subHead))return true;
else{
left = checkSubtree(head->left, subHead);
right = checkSubtree(head->right, subHead);
}
}else{
left = checkSubtree(head->left, subHead);
right = checkSubtree(head->right, subHead);
}
}
if(left || right)return true;
else return false;
}

Binary search on rotated array

int binarySearch(int *arr, int n, int start, int end){
int mid = start+(end - start)/2;
if(start<end){
if(n < arr[mid]){
if(n < arr[start])return binarySearch(arr, n, mid+1, end);
else return binarySearch(arr, n, start, mid-1);
}else{
if(n == arr[mid])return mid;
else{
if(n < arr[end])return binarySearch(arr, n, mid+1, end);
else return binarySearch(arr, n, start, mid-1);
}
}
}
}

Permute a string recursively

void recPermute(string sofar, string rest){
if(rest==""){
cout<<sofar<<endl;
}else{
for(int i=0;i<rest.length();i++){
string next = sofar+rest[i];
recPermute(next, rest.substr(0,i)+rest.substr(i+1));
}
}
}

Find height of the element in the tree

int maxH(int a, int b){
return (a>b)?a:b;
}

int height(node *ptr){
if(!ptr)return 0;
return maxH(height(ptr->left),height(ptr->right))+1;
}

Find Left Most element at each level in binary tree

int visited = -1;
void LeftMostInEveryLevel (node *root, int level) {
     if (root) {
              if (level > visited) {
                        cout << "Level = " << level << ", Node = " << root->data << endl;
                        visited = level;
              }
              LeftMostInEveryLevel (root->left, level + 1);
              LeftMostInEveryLevel (root->right, level + 1);
     }
}

Print out linked list of elements at each level of Binary Tree

queue<node *> q;
vector<node*> listVec;
int cntr = 0;
int level=0;

void convertLinkedList(node *ptr){
q.push(ptr);
cntr = 1;
while(!q.empty()){
level++;
int sz = cntr;
cntr = 0;
node *head = NULL;
node *prev = NULL;
for(int i = 0;i<sz;i++){
node *nd = q.front();
node *nn1 = new node;
nn1->data = q.front()->data;
nn1->right = NULL;
q.pop();
if(!head){
head = nn1;
prev = nn1;
}else{
prev->right = nn1;
prev = nn1;
}
if(nd->left || nd->right){
if(nd->left){
q.push(nd->left);
cntr++;
}
if(nd->right){
q.push(nd->right);
cntr++;
}
}
}
listVec.push_back(head);
}
}

BFS in Binary Tree

queue<node *> q ;
queue<node *> val;

void bfs(node *ptr){
q.push(ptr);
while(!q.empty()){
node *nd = q.front();
val.push(nd);
q.pop();
if(nd->left || nd ->right){
if(nd->left ){
q.push(nd->left);
}
if(nd->right){
q.push(nd->right);
}
}
}
}

Find Lowest Common Ancestor in BST

node *lca(node *root, int n1, int n2){
    if (!root) return NULL;
    if (root->data > n1 && root->data > n2)
        return lca(root->left, n1, n2);
    if (root->data < n1 && root->data < n2)
        return lca(root->right, n1, n2);
    return root;
}

Search in BST

bool search(node *T, int n){
if(T){
if(T->data == n)return true;
else{
if( n < T->data && T->left)return search(T->left, n);
else{
if(n > T->data && T->right) return search(T->right, n);
}
return false;
}
}
}

PostOrder(Recursive)

void postorder(node *T){
if(T){
postorder(T->left);
postorder(T->right);
cout<<T->data<<endl;
}
}

PreOrder(Recursive)

void preorder(node *T){
if(T){
cout<<T->data<<endl;
preorder(T->left);
preorder(T->right);
}
}

Inorder Traversal(Recursive)

void inorder(node *T){
if(T != NULL){
inorder(T->left);
cout<<T->data<<endl;
inorder(T->right);
}
}