bfs

Python3 Program to print BFS traversal

from a given source vertex. BFS(int s)

traverses vertices reachable from s.

from collections import defaultdict

This class represents a directed graph

using adjacency list representation

class Graph:

# Constructor
def __init__(self):

    # default dictionary to store graph
    self.graph = defaultdict(list)

# function to add an edge to graph
def addEdge(self,u,v):
    self.graph[u].append(v)

# Function to print a BFS of graph
def BFS(self, s):

    # Mark all the vertices as not visited
    visited = [False] * (max(self.graph) + 1)

    # Create a queue for BFS
    queue = []

    # Mark the source node as
    # visited and enqueue it
    queue.append(s)
    visited[s] = True

    while queue:

        # Dequeue a vertex from
        # queue and print it
        s = queue.pop(0)
        print (s, end = " ")

        # Get all adjacent vertices of the
        # dequeued vertex s. If a adjacent
        # has not been visited, then mark it
        # visited and enqueue it
        for i in self.graph[s]:
            if visited[i] == False:
                queue.append(i)
                visited[i] = True

Driver code

Create a graph given in

the above diagram

g = Graph() g.addEdge(0, 1) g.addEdge(0, 2) g.addEdge(1, 2) g.addEdge(2, 0) g.addEdge(2, 3) g.addEdge(3, 3)

print ("Following is Breadth First Traversal" " (starting from vertex 2)") g.BFS(2)

.............................................................................

DFS

// C++ program to print DFS traversal from // a given vertex in a given graph

include <bits/stdc++.h>

using namespace std;

// Graph class represents a directed graph // using adjacency list representation class Graph { public: map<int, bool> visited; map<int, list<int> > adj;

// function to add an edge to graph
void addEdge(int v, int w);

// DFS traversal of the vertices
// reachable from v
void DFS(int v);

};

void Graph::addEdge(int v, int w) { adj[v].push_back(w); // Add w to v’s list. }

void Graph::DFS(int v) { // Mark the current node as visited and // print it visited[v] = true; cout << v << " ";

// Recur for all the vertices adjacent
// to this vertex
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
    if (!visited[*i])
        DFS(*i);

}

// Driver code int main() { // Create a graph given in the above diagram Graph g; g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3);

cout << "Following is Depth First Traversal"
        " (starting from vertex 2) \n";
g.DFS(2);

return 0;

}

...........................................................

Find Diameter of a Binary Tree

.

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

def height(root, ans): if (root == None): return 0

left_height = height(root.left, ans)

right_height = height(root.right, ans)


ans[0] = max(ans[0], 1 + left_height +
                        right_height)

return 1 + max(left_height,
            right_height)

def diameter(root): if (root == None): return 0 ans = [-999999999999] # This will store

                    # the final answer
height_of_tree = height(root, ans)
return ans[0]

if __name__ == '__main__': root = newNode(1) root.left = newNode(2) root.right = newNode(3) root.left.left = newNode(4) root.left.right = newNode(5)

print("Diameter is", diameter(root))

FLATTEN BINARY TREE TO LL

class Node:

def __init__(self):

    self.key = 0
    self.left = None
    self.right = None

def newNode(key):

node = Node()
node.key = key
node.left = node.right = None
return (node)

def flatten(root):

if (root == None or root.left == None and
                    root.right == None):
    return


if (root.left != None):


    flatten(root.left)


    tmpRight = root.right
    root.right = root.left
    root.left = None


    t = root.right
    while (t.right != None):
        t = t.right


    t.right = tmpRight


flatten(root.right)

def inorder(root):

if (root == None):
    return

inorder(root.left)
print(root.key, end = ' ')
inorder(root.right)

if __name__=='__main__':

root = newNode(1)
root.left = newNode(2)
root.right = newNode(5)
root.left.left = newNode(3)
root.left.right = newNode(4)
root.right.right = newNode(6)

flatten(root)

print("The Inorder traversal after "
    "flattening binary tree ",
    end = '')
inorder(root)

SORTED ARRAY TO BALANCED BST

include<bits/stdc++.h>

using namespace std;

class TNode { public: int data; TNode left; TNode right; };

TNode* newNode(int data);

TNode* sortedArrayToBST(int arr[], int start, int end) {

if (start > end)
return NULL;


int mid = (start + end)/2;
TNode *root = newNode(arr[mid]);


root->left = sortedArrayToBST(arr, start,mid - 1);

root->right = sortedArrayToBST(arr, mid + 1, end);

return root;

}

TNode newNode(int data) { TNode node = new TNode(); node->data = data; node->left = NULL; node->right = NULL;

return node;

}

void preOrder(TNode* node) { if (node == NULL) return; cout << node->data << " "; preOrder(node->left); preOrder(node->right); }

int main() { int arr[] = {1, 2, 3, 4, 5, 6, 7}; int n = sizeof(arr) / sizeof(arr[0]);

TNode *root = sortedArrayToBST(arr, 0, n-1);
cout << "PreOrder Traversal of constructed BST \n";
preOrder(root);

return 0;

}

Kth Largest element in bst

class Node:

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

def kthLargestUtil(root, k, c):

if root == None or c[0] >= k:  
    return


kthLargestUtil(root.right, k, c) 


c[0] += 1


if c[0] == k: 
    print("K'th largest element is",  
                           root.key)  
    return


kthLargestUtil(root.left, k, c)

def kthLargest(root, k):

c = [0] 


kthLargestUtil(root, k, c)

def insert(node, key):

if node == None: 
    return Node(key)  


if key < node.key:  
    node.left = insert(node.left, key)  
elif key > node.key: 
    node.right = insert(node.right, key)  


return node

if __name__ == '__main__':

root = None
root = insert(root, 50) 
insert(root, 30) 
insert(root, 20) 
insert(root, 40) 
insert(root, 70) 
insert(root, 60) 
insert(root, 80) 

for k in range(1,8): 
    kthLargest(root, k)

Minimum absolute difference in BST

import math

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

def inorder(curr, prev): global ans

if (curr == None):
    return


inorder(curr.left, prev)

if (prev != None):
    ans = min(curr.data - prev.data, ans)
prev = curr


inorder(curr.right, prev)

def minDiff(root):

prev = None


global ans
ans = math.inf


inorder(root, prev)


return ans

if __name__ == '__main__':

root = node(5)
root.left = node(3)
root.right = node(7)
root.left.left = node(2)
root.left.right = node(4)
root.right.left = node(6)
root.right.right = node(8)

print(minDiff(root))

Merge Two BST

include<bits/stdc++.h>

using namespace std;

class node { public: int data; node left; node right; };

int *merge(int arr1[], int arr2[], int m, int n);

void storeInorder(node node, int inorder[], int index_ptr);

node* sortedArrayToBST(int arr[], int start, int end);

node mergeTrees(node root1, node *root2, int m, int n) {

int *arr1 = new int[m];
int i = 0;
storeInorder(root1, arr1, &i);


int *arr2 = new int[n];
int j = 0;
storeInorder(root2, arr2, &j);


int *mergedArr = merge(arr1, arr2, m, n);


return sortedArrayToBST (mergedArr, 0, m + n - 1);

}

node newNode(int data) { node Node = new node(); Node->data = data; Node->left = NULL; Node->right = NULL;

return(Node);

}

void printInorder(node* node) { if (node == NULL) return;

printInorder(node->left);

cout << node->data << " ";


printInorder(node->right);

}

int *merge(int arr1[], int arr2[], int m, int n) {

int *mergedArr = new int[m + n];
int i = 0, j = 0, k = 0;


while (i < m && j < n)
{

    if (arr1[i] < arr2[j])
    {
        mergedArr[k] = arr1[i];
        i++;
    }
    else
    {
        mergedArr[k] = arr2[j];
        j++;
    }
    k++;
}

while (i < m)
{
    mergedArr[k] = arr1[i];
    i++; k++;
}


while (j < n)
{
    mergedArr[k] = arr2[j];
    j++; k++;
}

return mergedArr;

}

void storeInorder(node node, int inorder[], int index_ptr) { if (node == NULL) return;

storeInorder(node->left, inorder, index_ptr);

inorder[*index_ptr] = node->data;
(*index_ptr)++;

storeInorder(node->right, inorder, index_ptr);

}

node* sortedArrayToBST(int arr[], int start, int end) {

if (start > end)
return NULL;


int mid = (start + end)/2;
node *root = newNode(arr[mid]);


root->left = sortedArrayToBST(arr, start, mid-1);


root->right = sortedArrayToBST(arr, mid+1, end);

return root;

}

int main() {

node *root1 = newNode(100);
root1->left  = newNode(50);
root1->right = newNode(300);
root1->left->left = newNode(20);
root1->left->right = newNode(70);


node *root2 = newNode(80);
root2->left  = newNode(40);
root2->right = newNode(120);

node *mergedTree = mergeTrees(root1, root2, 5, 3);

cout << "Following is Inorder traversal of the merged tree \n";
printInorder(mergedTree);

return 0;

}

SLIDING MAXIMUM WINDOW

def find_max(a): m=a[0] for i in range(0,len(a)): if(a[i]>m): m=a[i] return m

def max_num(arr,k): maxs=0 x=list() for j in range(0,len(arr)-k+1):

    #print(j)
    smax_arr=arr[j:j+k]
    print(smax_arr)
    smax=find_max(smax_arr)
    if(smax>maxs):
        max_arr=smax_arr
        maxs=smax
    x.append(maxs)
return x

arr=[4,3,8,9,0,1,10,4,2,5,11] print(max_num(arr,4))

MERGE K SORTED LIST

class Node:

def __init__(self, x):

    self.data = x
    self.next = None

def printList(node):

while (node != None):
    print(node.data,
        end = " ")
    node = node.next

def mergeKLists(arr, last):

for i in range(1, last + 1):
    while (True):

        head_0 = arr[0]
        head_i = arr[i]


        if (head_i == None):
            break


        if (head_0.data >=
            head_i.data):
            arr[i] = head_i.next
            head_i.next = head_0
            arr[0] = head_i
        else:

            while (head_0.next != None):

                if (head_0.next.data >=
                    head_i.data):
                    arr[i] = head_i.next
                    head_i.next = head_0.next
                    head_0.next = head_i
                    break

                head_0 = head_0.next

                if (head_0.next == None):
                    arr[i] = head_i.next
                    head_i.next = None
                    head_0.next = head_i
                    head_0.next.next = None
                    break
return arr[0]

if __name__ == '__main__':

k = 3


n = 4


arr = [None for i in range(k)]

arr[0] = Node(1)
arr[0].next = Node(3)
arr[0].next.next = Node(5)
arr[0].next.next.next = Node(7)

arr[1] = Node(2)
arr[1].next = Node(4)
arr[1].next.next = Node(6)
arr[1].next.next.next = Node(8)

arr[2] = Node(0)
arr[2].next = Node(9)
arr[2].next.next = Node(10)
arr[2].next.next.next = Node(11)

head = mergeKLists(arr, k - 1)

printList(head)

MIN HEAP TO MAX HEAP

def MaxHeapify(arr, i, n): l = 2 i + 1 r = 2 i + 2 largest = i if l < n and arr[l] > arr[i]: largest = l if r < n and arr[r] > arr[largest]: largest = r if largest != i: arr[i], arr[largest] = arr[largest], arr[i] MaxHeapify(arr, largest, n)

def convertMaxHeap(arr, n):

for i in range(int((n - 2) / 2), -1, -1):
    MaxHeapify(arr, i, n)

def printArray(arr, size): for i in range(size): print(arr[i], end = " ") print()

if __name__ == '__main__':

arr = [3, 5, 9, 6, 8, 20, 10, 12, 18, 9]
n = len(arr)

print("Min Heap array : ")
printArray(arr, n)

convertMaxHeap(arr, n)

print("Max Heap array : ")
printArray(arr, n)