[go: up one dir, main page]

0% found this document useful (0 votes)
12 views7 pages

Heaps BST

Uploaded by

abhi3hack
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
12 views7 pages

Heaps BST

Uploaded by

abhi3hack
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 7

K Largest Elements

class Solution:
# @param A : list of integers
# @param B : integer
# @return a list of integers

def solve(self, A, B):


import heapq as hp
hp.heapify(A)
for i in range(len(A)-B):
hp.heappop(A)
return A

Profit Maximisation

import heapq

class Solution:
# @param A : list of integers
# @param B : integer
# @return an integer
def solve(self, A, B):
cost = 0
A = [-el for el in A]
heapq.heapify(A)

for i in range(B):
smallest = A[0]
heapq.heapreplace(A, A[0] + 1)
cost += abs(smallest)

return cost

Perfect example to understand hashing using dict


Distinct Numbers in Window

class Solution:
# @param A : list of integers
# @param B : integer
# @return a list of integers
def dNums(self, A, B):
seen = {}
res = list()
ptrs = [None]*len(A)
for i in range(B):
seen[A[i]] = i
res.append(len(seen))
for i in range(B, len(A)):
if seen[A[i-B]]==i-B:
del seen[A[i-B]]
seen[A[i]] = i

res.append(len(seen))
return res

Solving maxheap logic using minheap from heapq

from heapq import *

class Solution:
# @param A : integer
# @param B : list of integers
# @return an integer
def nchoc(self, A, B):
h = [-b for b in B]
heapify(h)
s = 0
for _ in range(A):
chocs = -heappop(h)
s = (s + chocs) % 1000000007
heappush(h, -(chocs // 2))
return s

1) The maximum number of nodes at level ‘l’ of a binary tree is 2l.


2) The Maximum number of nodes in a binary tree of height ‘h’ is 2h – 1.
3) In a Binary Tree with N nodes, minimum possible height or the minimum number of
levels is Log2(N+1).
4) A Binary Tree with L leaves has at least | Log2L |+ 1 levels.
5) In Binary tree where every node has 0 or 2 children, the number of leaf nodes is
always one more than nodes with two children.
6) In a non empty binary tree, if n is the total number of nodes and e is the total
number of edges, then e = n-1

Kth Smallest Element In Tree

# Definition for a binary tree node


# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param A : root node of tree
# @param B : integer
# @return an integer

def kthsmallest(self, A, B):


left_branch = []
while A:
left_branch.append(A)
A = A.left

for _ in range(B):
rtn = left_branch.pop()
node = rtn.right
while node:
left_branch.append(node)
node = node.left
return rtn.val

Burn a Tree

# Definition for a binary tree node


# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
# @param A : root node of tree
# @param B : integer
# @return an integer
def solve(self, A, B):
def bottom_up(node, starting):
if not node: return 0, False # think 2 nodes total:
root -> initial
if node.val == starting: return 1, True # initial leaf; leaaf
always return 1

time_left, burn_left = bottom_up(node.left, starting)


time_right, burn_right = bottom_up(node.right, starting)

burn = burn_left or burn_right # if not include


initial burn leaf:
if not burn: return 1 + max(time_left, time_right), False # return
subtree depth

curr = time_left + time_right # initial leaf to curr + other


side depth
if self.time < curr: self.time = curr # need check each nodes in
main_path !!!
return 1 + (time_left if burn_left else time_right), True

import sys
sys.setrecursionlimit(10**4) # as 2 <= number of nodes <= 10 ^ 5

self.time = 0
bottom_up(A, B) # A: root, B: initial leaf
return self.time

Max Depth of Binary Tree

# Definition for a binary tree node


# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
# @param A : root node of tree
# @return an integer
def maxDepth(self, A):
if not A:
return 0
return 1 + max(self.maxDepth(A.left), self.maxDepth(A.right))

Sorted Array To Balanced BST

# Definition for a binary tree node


# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
# @param A : tuple of integers
# @return the root node in the tree
def sortedArrayToBST(self, A):
if len(A) == 0:
return None
mid = len(A)/2
root = TreeNode(A[mid])
root.left = self.sortedArrayToBST(A[:mid])
root.right = self.sortedArrayToBST(A[mid+1:])
return root

# A function to do inorder tree traversal


def printInorder(root):
if root:
# First recur on left child
printInorder(root.left)
# then print the data of node
print(root.val),
# now recur on right child
printInorder(root.right)

# A function to do postorder tree traversal


def printPostorder(root):
if root:
# First recur on left child
printPostorder(root.left)
# the recur on right child
printPostorder(root.right)
# now print the data of node
print(root.val),

# A function to do preorder tree traversal


def printPreorder(root):
if root:
# First print the data of node
print(root.val),
# Then recur on left child
printPreorder(root.left)
# Finally recur on right child
printPreorder(root.right)

DFS and BFS :


def dfs(self, node, par = None):
if node:
node.par = par
self.dfs(node.left, node)
self.dfs(node.right, node)

def bfs(self, src, x):


if(src):
if(src.val == x):
self.target = src
self.bfs(src.left, x)
self.bfs(src.right, x)

vertical traversal of nodes

class Solution:
# @param A : root node of tree
# @return a list of list of integers
def verticalOrderTraversal(self, A):
if A == None:
return []

queue = [(A,0)]
ans = {} # dict x -> [values] for current level
# Iterate by level, so values are properly stacked.
while queue:
queue2 = []
for node, x in queue:
ans.setdefault(x,[]).append(node.val)
if node.left is not None:
queue2.append((node.left, x-1))
if node.right is not None:
queue2.append((node.right, x+1))
queue = queue2

return [ans[x] for x in sorted(ans.keys())]

Get the path to the node from the root:

def getPath(self,root, value):


if root==None:
return []
if root.val == value :
return [root]
left = self.getPath(root.left, value)
right = self.getPath(root.right, value)

if right:
return [root] + right
if left:
return [root] + left
return []

Diagnol traversal:
select a node and store its left child node and add go towards right leaf node
class Solution:
# @param A : root node of tree
# @return a list of integers
def solve(self, A):
res = []
roots = [A]
while len(roots)>0:
new_roots = []
for node in roots:
while node is not None:
new_roots.append(node.left)
res.append(node.val)
node = node.right
roots = new_roots
return res

Right view of Binary tree

# Definition for a binary tree node


# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
# @param A : root node of tree
# @return a list of integers
def solve(self, A):
result = []
previous = [A]
while previous:
result.append(previous[-1].val)
current = []
for node in previous:
if node.left:
current.append(node.left)
if node.right:
current.append(node.right)
previous = current
return result

You might also like