from IPython.display import SVG, HTML
from IPython.display import display
from graphviz import Source
from collections import deque
from typing import List
from numpy import inf
import operator
import codecs
import os
import re
def visualize(text, height=220):
text = "digraph BST_TEMP {" + text + "}"
graph = Source(text)
svgt = codecs.decode(graph.pipe(format='svg'),'UTF-8')
regex_1 = r"height=\"[0-9]+pt\""
regex_2 = r"width=\"[0-9]+pt\""
subst = 'height="'+str(height)+'pt"'
svgt = re.sub(regex_1, subst, svgt, 0, re.MULTILINE)
svgt = re.sub(regex_2, subst, svgt, 0, re.MULTILINE)
display(HTML("<br>"+svgt))
def arrow_string(a, b):
return (str(a) + "->" + str(b) + ";")
def binary_search(items:List[int], key, start=0, end=None) -> int:
"""
Return index if found and -1 otherwise.
"""
if end is None:
end = len(items)-1
if start > end:
return -1
mid = (start + end)//2
if items[mid] == key:
return mid
elif items[mid] > key:
return binary_search(items, key=key, start=start, end=mid-1)
elif items[mid] < key:
return binary_search(items, key=key, start=mid+1, end=end)
# Method Call
binary_search([1,2,3], key=2)
1
In a BST parent, left nodes contain larger values or a right node contain smaller values
# Node Class
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def insert(self, data):
if self.data:
# Left Nodes
if self.data > data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
# Right Nodes
elif self.data < data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
# Root Node
self.data = data
# BST Traversal - In-order
# Left -> Root -> Right
def print_inorder(self):
if self.left:
self.left.print_inorder()
print(self.data, end=" ")
if self.right:
self.right.print_inorder()
# Return the number of children for a parent (range: 0-2)
def get_children_count(self):
count = 0
if self.left: count+=1
if self.right: count+=1
return count
def display_bst(root, height=220):
global text
text = ""
_print_child_parent_pair(root)
visualize(text, height)
def _print_child_parent_pair(root, parent=None):
global text
if root.left:
text += arrow_string(root.data, root.left.data)
if root.right:
text += arrow_string(root.data, root.right.data)
if root.left:
_print_child_parent_pair(root.left, root.data)
if root.right:
_print_child_parent_pair(root.right, root.data)
# Return Minimum
def get_min_node(root):
if root.left is None:
return root
return get_min_node(root.left)
# Delete Operation
def delete_bst(root, data):
if root is None:
return root
if(data > root.data):
root.right = delete_bst(root.right, data)
elif(data < root.data):
root.left = delete_bst(root.left, data)
else:
# Node with only one child or no child
if root.left is None:
temp = root.right
root = None
return temp
elif root.right is None:
temp = root.left
root = None
return temp
# Two Child
temp = get_min_node(root.right)
root.data = temp.data
root.right = delete_bst(root.right, temp.data)
return root
""" First depth occurances while In-order Traversing will return all Left view
elements. Sort the Key-Value pair based on depth in ascending order.
"""
def print_left_view(root):
left_view = {}
left_view = _print_left_view(root, left_view)
print([v for (k, v) in sorted(left_view.items())])
def _print_left_view(root, left_view, depth=-1):
depth += 1
if root.left:
_print_left_view(root.left, left_view, depth)
if depth not in left_view.keys():
left_view[depth] = root.data
if root.right:
_print_left_view(root.right, left_view, depth)
return left_view
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def return_nodes(self, root, bits_text, ans_temp, depth):
global depth_max
depth += 1
depth_max = max(depth, depth_max)
bits_text += str(root.val)
if root.left:
self.return_nodes(root.left, bits_text, ans_temp, depth)
if root.right:
self.return_nodes(root.right, bits_text, ans_temp, depth)
ans_temp.append(bits_text)
return ans_temp
def sumRootToLeaf(self, root) -> int:
global depth_max
depth_max = -1
ans_t = self.return_nodes(root, "", [], -1)
depth_max = depth_max + 1
sum = 0
for (i, j) in enumerate(ans_t):
if len(j) == depth_max:
print(j, end=" ")
sum += (int(j, 2))
return sum
elements = [50, 30, 20, 40, 70, 60, 80, 85, 86, 79]
root = Node(elements[0])
for i in range(1, len(elements)): root.insert(elements[i])
display_bst(root)
print_left_view(root)
[50, 30, 20, 79, 86]
# Removing node with no children
delete_bst(root, 20)
display_bst(root)
# Removing node with 1 child
delete_bst(root, 30)
display_bst(root)
# Removing node with 2 children
delete_bst(root, 50)
display_bst(root)
# For Visualizing Graphs
def display_graph(graph, height=200):
text ="overlap = false; edge [arrowhead=none,arrowtail=none];"
for i in graph:
for j in graph[i]:
text += arrow_string(i, j)
visualize(text,height)
graph_1 = {
'1': set(['2', '3']),
'2': set(['4', '5']),
'3': set([]),
'4': set([]),
'5': set([]),
}
graph_2 = {
'0': set(['1', '2']),
'1': set(['0', '3', '4']),
'2': set(['0']),
'3': set(['1']),
'4': set(['2', '3']),
}
graph_3 = {
'2': set([]),
'3': set(['2', '4']),
'4': set(['8']),
'5': set(['3', '7']),
'7': set(['8']),
'8': set([]),
}
display_graph(graph_1)
# We use sets since it cannot have duplicates
def dfs(graph, start, visited=None):
if visited is None:
print("Path: ", end=" ")
visited = set()
visited.add(start)
print(start, end=" ")
for next in graph[start]-visited:
dfs(graph, next, visited)
return visited
visited = dfs(graph_1, '1')
print("\nVisited: ", end=" ")
for v in visited: print(v, end=" ")
Path: 1 2 4 5 3 Visited: 1 3 2 4 5
# We use sets since it cannot have duplicates
def bfs(graph, start):
try:
queue = []
path = []
visited = set()
visited.add(start)
queue.append(start)
while queue:
m = queue.pop(0)
path.append(m)
for next in graph[m]-visited:
visited.add(next)
queue.append(next)
return path
except KeyError:
print("Node", m, "does not exist")
return [None]
visited = bfs(graph_1, '1')
print("Path: ", end=" ")
for v in visited: print(v, end=" ")
Path: 1 2 3 4 5
Given a graph and a source vertex in the graph, find shortest paths from source to all vertices in the given graph. Works only on Positive Weighted Graphs.
# For Visualizing Graphs
def display_wd_graph(graph, height=200):
text ="rankdir=LR; overlap=scale;"
for i in graph:
for j in graph[i]:
w_t = '[label="'+str(graph[i][j])+'"];'
text += arrow_string(i, j)[:-1] + w_t
visualize(text,height)
# Weigted Graphs
graph_wd_1 = {
'A': {'C': 5, 'D': 1, 'E': 2},
'B': {'G': 3, 'H': 1},
'C': {'A': 5, 'D': 3, 'I': 2},
'D': {'A': 1, 'C': 3, 'H': 2},
'E': {'A': 2, 'F': 3},
'F': {'E': 3, 'G': 1},
'G': {'B': 3, 'F': 1, 'H': 2},
'H': {'B': 1, 'D': 2, 'G': 2, 'I': 2},
'I': {'C': 2, 'H': 2}}
graph_wd_2 = {
'B': {'A': 5, 'D': 1, 'G': 2},
'A': {'B': 5, 'D': 3, 'E': 12, 'F' :5},
'D': {'B': 1, 'G': 1, 'E': 1, 'A': 3},
'G': {'B': 2, 'D': 1, 'C': 2},
'C': {'G': 2, 'E': 1, 'F': 16},
'E': {'A': 12, 'D': 1, 'C': 1, 'F': 2},
'F': {'A': 5, 'E': 2, 'C': 16}}
display_wd_graph(graph_wd_2, 300)
def dijkstras(graph, source):
global cost, parent, visited
cost = {}
parent = {}
visited = set()
# inf imported from numpy
for key in graph.keys(): cost[key] = inf
cost[source] = 0
_dijkstras(graph, source)
cost = sorted(cost.items(), key=operator.itemgetter(1))
return cost
def _dijkstras(graph, source):
global cost, parent, visited
if source is None:
return
visited.add(source)
for neighbour in graph[source]:
if graph[source][neighbour] + cost[source] < cost[neighbour]:
cost[neighbour] = graph[source][neighbour] + cost[source]
parent[neighbour] = source
minw = inf
mink = None
for k in parent.keys():
if minw > cost[k] and k not in visited:
minw = cost[k]
mink = k
_dijkstras(graph, mink)
dijkstras(graph_wd_2, "B")
[('B', 0), ('D', 1), ('G', 2), ('E', 2), ('C', 3), ('A', 4), ('F', 4)]