Dyck path

def countDyckPaths(n):

res = 1

for i in range(0, n):

res *= (2 * n - i)

res /= (i + 1)

return res / (n+1)

n = 4

print("Number of Dyck Paths is ",

str(int(countDyckPaths(n))))

Longest path between any pair of vertices

def DFS(graph, src, prev_len,

max_len, visited):

visited[src] = 1

curr_len = 0

adjacent = None

for i in range(len(graph[src])):

adjacent = graph[src][i]

if (not visited[adjacent[0]]):

curr_len = prev_len + adjacent[1]

DFS(graph, adjacent[0], curr_len,

max_len, visited)

if (max_len[0] < curr_len):

max_len[0] = curr_len

curr_len = 0

def longestCable(graph, n):

max_len = [-999999999999]

for i in range(1, n + 1):

visited = [False] * (n + 1)

DFS(graph, i, 0, max_len, visited)

return max_len[0]

if __name__ == '__main__':

n = 6

graph = [[] for i in range(n + 1)]

graph[1].append([2, 3])

graph[2].append([1, 3])

graph[2].append([3, 4])

graph[3].append([2, 4])

graph[2].append([6, 2])

graph[6].append([2, 2])

graph[4].append([6, 6])

graph[6].append([4, 6])

graph[5].append([6, 5])

graph[6].append([5, 5])

print("Maximum length of cable =",

longestCable(graph, n))

Reverse a path in Binary search tree using queue

class Node:

def __init__(self, data):

self.key = data

self.left = None

self.right = None

def inorder(root):

if root != None:

inorder(root.left)

print(root.key, end = " ")

inorder(root.right)

def reversePath(node, key, q1):

if node == None:

return

if node.key == key:

q1.insert(0, node.key)

node.key = q1[-1]

q1.pop()

return

elif key < node.key:

q1.insert(0, node.key)

reversePath(node.left, key, q1)

node.key = q1[-1]

q1.pop()

elif (key > node.key):

q1.insert(0, node.key)

reversePath(node.right, key, q1)

node.key = q1[-1]

q1.pop()

return

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

q1 = []

k = 80;

root = insert(root, 50)

insert(root, 30)

insert(root, 20)

insert(root, 40)

insert(root, 70)

insert(root, 60)

insert(root, 80)

print("Before Reverse :")

inorder(root)

reversePath(root, k, q1)

print()

print("After Reverse :")

inorder(root)

Python for Engineers featured in Feedspot Top 60 Python Blogs

Python for Engineers has been selected by Feedspot as one of the Top 60 Python Blogs on the web 

https://blog.feedspot.com/python_blogs/

creating mergeable stack

class Node():

def __init__(self,data):

self.next = None

self.prev = None

self.data = data

class Stack():

def __init__(self):

self.head = None

self.tail = None

def push(self, data):

new_node = Node(data)

if (self.head == None):

self.head = new_node

self.head.next= None

self.head.prev = None

self.tail = new_node

else:

new_node.prev = self.tail

self.tail.next = new_node

self.tail = new_node

def pop(self):

if (self.head == None):

print("Stack underflow")

if (self.head == self.tail):

self.head = None

self.tail = None

else:

node = self.tail

self.tail = self.tail.prev

del node

self.tail.next = None

def merge(self, stack):

if stack.head == None: return 

if self.head == None:

self.head = stack.head

self.tail = stack.tail

return

self.head.prev = stack.tail 

stack.tail.nxt = self.head

self.head = stack.head

def display(self):

if (self.tail != None):

n = self.tail

while (n != None):

print(n.data, end = " ")

n = n.prev

print()

else:

print("Stack Underflow")

ms1 = Stack()

ms2 = Stack()

ms1.push(6)

ms1.push(5)

ms1.push(4)

ms2.push(9)

ms2.push(8)

ms2.push(7)

ms1.merge(ms2)

ms1.display()

while ms1.head != ms1.tail:

ms1.pop ()

print ("check pop all elements until head == tail (one element left)")

print ("on merged stack: ", end = "")

ms1.display()