Input : Inorder -> 4 2 5 1 3
Preorder -> 1 2 4 5 3
Postorder -> 4 5 2 3 1
Output : Yes
Exaplanation : All of the above three traversals are of
the same tree 1
/ \
2 3
/ \
4 5
Input : Inorder -> 4 2 5 1 3
Preorder -> 1 5 4 2 3
Postorder -> 4 1 2 3 5
Output : No
''' Deque for graphs '''
import collections
def breadth_first_search(graph, root):
visited, queue = set(), collections.deque([root])
while queue:
vertex = queue.popleft()
yield vertex
visited.add(vertex)
queue.extend(n for n in graph[vertex] if n not in visited)
if __name__ == '__main__':
graph = {1: [2, 4, 5], 2: [3, 6, 7], 3: [], 4: [], 5: [], 6: [], 7: []}
list(breadth_first_search(graph, 1)) # [1, 2, 4, 5, 3, 6, 7]Quicksort
# This function takes last element as pivot, places
# the pivot element at its correct position in sorted
# array, and places all smaller (smaller than pivot)
# to left of pivot and all greater elements to right
# of pivot
def partition(arr,low,high):
i = ( low-1 ) # index of smaller element
pivot = arr[high] # pivot
for j in range(low , high):
# If current element is smaller than or
# equal to pivot
if arr[j] <= pivot:
# increment index of smaller element
i = i+1
arr[i],arr[j] = arr[j],arr[i]
arr[i+1],arr[high] = arr[high],arr[i+1]
return ( i+1 )
# The main function that implements QuickSort
# arr[] --> Array to be sorted,
# low --> Starting index,
# high --> Ending index
# Function to do Quick sort
def quickSort(arr,low,high):
if low < high:
# pi is partitioning index, arr[p] is now
# at right place
pi = partition(arr,low,high)
# Separately sort elements before
# partition and after partition
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)