<jupyter_start><jupyter_text>Mod 1  balancedBinaryTree

You are given a binary tree and you need to write a function that can determine if it is height-balanced.

A height-balanced tree can be defined as a binary tree in which the left and right subtrees of every node differ in height by a maximum of 1.

Example 1:
Given the following tree [5,10,25,None,None,12,3]:

    5
   / \
 10  25
    /  \
   12   3

return True.

Example 2:
Given the following tree [5,6,6,7,7,None,None,8,8]:

       5
      / \
     6   6
    / \
   7   7
  / \
 8   8


return False.

[execution time limit] 4 seconds (py3)

[input] tree.integer root

[output] boolean<jupyter_code># Binary trees are already defined with this interface:
# class Tree(object):
#   def __init__(self, x):
#     self.value = x
#     self.left = None
#     self.right = None

def depth(root):
    if not root: 
        return 0
    return max(depth(root.left), depth(root.right)) + 1
  

def balancedBinaryTree(root):
    if not root: 
        return True
    left_depth = depth(root.left) 
    right_depth = depth(root.right)
    return (abs(left_depth - right_depth) <= 1) and balancedBinaryTree(root.left) and balancedBinaryTree(root.right)<jupyter_output><empty_output><jupyter_text>minimumDepthBinaryTree

You are given a binary tree and you are asked to write a function that finds its minimum depth. The minimum depth can be defined as the number of nodes along the shortest path from the root down to the nearest leaf node. As a reminder, a leaf node is a node with no children.

Example:
Given the binary tree [5,7,22,None,None,17,9],
    5
   / \
  7  22
    /  \
   17   9

your function should return its minimum depth = 2.

[execution time limit] 4 seconds (py3)

[input] tree.integer root

[output] integer<jupyter_code># Binary trees are already defined with this interface:
# class Tree(object):
#   def __init__(self, x):
#     self.value = x
#     self.left = None
#     self.right = None
def minimumDepthBinaryTree(root):
    if root is None: 
        return 0 
    if not root.left and not root.right: 
        return 1
    if not root.left: #call again on right 
        return minimumDepthBinaryTree(root.right)+1
    if not root.right: #call again on left
        return minminimumDepthBinaryTreeDepth(root.left) +1 
    # if none of these are true anymore, exit recursion & return the minimum
    return min(minimumDepthBinaryTree(root.left), minimumDepthBinaryTree(root.right))+1<jupyter_output><empty_output><jupyter_text>Mod 2
  traverseTree

Given a binary tree of integers t, return its node values in the following format:

The first element should be the value of the tree root;
The next elements should be the values of the nodes at height 1 (i.e. the root children), ordered from the leftmost to the rightmost one;
The elements after that should be the values of the nodes at height 2 (i.e. the children of the nodes at height 1) ordered in the same way;
Etc.
Example

For
t = {
    "value": 1,
    "left": {
        "value": 2,
        "left": null,
        "right": {
            "value": 3,
            "left": null,
            "right": null
        }
    },
    "right": {
        "value": 4,
        "left": {
            "value": 5,
            "left": null,
            "right": null
        },
        "right": null
    }
}

the output should be
traverseTree(t) = [1, 2, 4, 3, 5].

This t looks like this:

     1
   /   \
  2     4
   \   /
    3 5<jupyter_code>def traverseTree(t):
    if not t:
        return []
    result = []
    queue = []
    queue.append(t)
    while len(queue) != 0:
        node = queue.pop(0)
        result.append(node.value)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result<jupyter_output><empty_output><jupyter_text>binaryTreeInOrderTraversal

You are given a binary tree. Write a function that returns the binary tree's node values using an in-order traversal.

Example:
Input: [2,None,3,4]
   2
    \
     3
    /
   4

Output: [2,4,3]<jupyter_code>def helper(root, res):
    if not root:
        return
    helper(root.left, res)
    res.append(root.value)
    helper(root.right, res)
    
def binaryTreeInOrderTraversal(root):
    result = []
    helper(root, result)
    return result<jupyter_output><empty_output><jupyter_text>treePaths

Given a binary tree of integers, return all the paths from the tree's root to its leaves as an array of strings. The strings should have the following format:
"root->node1->node2->...->noden", representing the path from root to noden, where root is the value stored in the root and node1,node2,...,noden are the values stored in the 1st, 2nd,..., and nth nodes in the path respectively (noden representing the leaf).

Example

For

t = {
    "value": 5,
    "left": {
        "value": 2,
        "left": {
            "value": 10,
            "left": null,
            "right": null
        },
        "right": {
            "value": 4,
            "left": null,
            "right": null
        }
    },
    "right": {
        "value": -3,
        "left": null,
        "right": null
    }
}


The given tree looks like this:

    5
   / \
  2  -3
 / \
10  4<jupyter_code># Binary trees are already defined with this interface:
# class Tree(object):
#   def __init__(self, x):
#     self.value = x
#     self.left = None
#     self.right = None
def treePaths(t): 
    # list to store path 
    path = [] 
    result = []
    getPath(t, path, 0, result)
    return result

def getPath(t, path, pathLen, result): 
    if t is None: 
        return
    if(len(path) > pathLen):  
        # replace element in list
        path[pathLen] = t.value 
    else: 
        #add to end of list
        path.append(t.value) 
    pathLen = pathLen + 1
    
    if t.left is None and t.right is None: 
        addString(path, result, pathLen) 
    else: 
        getPath(t.left, path, pathLen, result) 
        getPath(t.right, path, pathLen, result) 

def addString(ints,res, pathLen): 
    s = ""
    for i in range(pathLen):
        s+=(str(ints[i])+"->") 
    res.append(s[:-2])
    return res<jupyter_output><empty_output><jupyter_text>Lecture
  Recursive Max Depth<jupyter_code># 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

### https://leetcode.com/problems/maximum-depth-of-binary-tree/


class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        self.maxDepth = 0
        self.maxDepthHelper(root, 1)
        return self.maxDepth
    
    def maxDepthHelper(self, root, currDepth):
        if root.left == None and root.right == None:
            if currDepth > self.maxDepth:
                self.maxDepth = currDepth
            return
        self.maxDepthHelper(root.left, currDepth+1)
        self.maxDepthHelper(root.right, currDepth+1)<jupyter_output><empty_output><jupyter_text>Iterative Max Depth<jupyter_code># 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
from collections  import deque

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root == None:
            return 0
        stack = deque()
        stack.append((root, 1))
        maxDepthFound = 1
        while len(stack) > 0:
            curr = stack.pop()
            currNode, currDepth = curr[0], curr[1]
            if currNode.left == None and currNode.right == None:
                if currDepth > maxDepthFound:
                    maxDepthFound = currDepth
            if currNode.left != None:
                stack.append((currNode.left, currDepth + 1))
            if currNode.right != None:
                stack.append((currNode.right, currDepth + 1))
        return maxDepthFound<jupyter_output><empty_output><jupyter_text>Mod 3
  Graph Class code<jupyter_code>class Vertex:
    def __init__(self, value):
        self.value = value
        self.connections = {}

    def __str__(self):
        return str(self.value) + ' connections: '+str([x.value for x in self.connections])

    def add_connection(self, vert, weight = 0):
        self.connections[vert] = weight

    def get_connections(self):
        return self.connections.keys()

    def get_value(self):
        return self.value

    def get_weight(self, vert):
        return self.connections[vert]

class Graph:
    def __init__(self):
        self.vertices = {}
        self.count = 0

    def __contains__(self, vert):
        return vert in self.vertices

    def __iter__(self):
        return iter(self.vertices.values())

    def add_vertex(self, value):
        self.count += 1
        new_vert = Vertex(value)
        self.vertices[value] = new_vert
        return new_vert

    def add_edge(self, v1, v2, weight = 0):
        if v1 not in self.vertices:
            self.add_vertex(v1)
        if v2 not in self.vertices:
            self.add_vertex(v2)
        self.vertices[v1].add_connection(self.vertices[v2], weight)

    def get_vertices(self):
        return self.vertices.keys()
if 5 not in [1,3]:
  print('not')
else : print('in')<jupyter_output>not<jupyter_text>You are given a directed acyclic graph (DAG) that contains N nodes.

Write a function that can find all the possible paths from node 0 to node N - 1.

graph[a] is a list of all nodes b for which the edge a -> b exists.

Example:


Input: graph = [[1, 2],[3],[3],[4],[]]
Output: [[0,1,3,4], [0,2,3,4]]

Note: The results must be returned in sorted order. You can use any built-in sort method on the results array at the end of your function before returning.<jupyter_code>from collections import defaultdict, deque # defaultdict was my downfall. 
import random                              # lessons learned, more practice
                                           # needed with graphs and deque

# def append_value(dict_obj, key, value):
#     # Check if key exist in dict or not
#     if key in dict_obj:
#         # Key exist in dict.
#         # Check if type of value of key is list or not
#         if not isinstance(dict_obj[key], list):
#             # If type is not list then make it list
#             dict_obj[key] = [dict_obj[key]]
#         # Append the value in list
#         dict_obj[key].append(value)
#     else:
#         # As key is not in dict,
#         # so, add key-value pair
#         dict_obj[key] = value

# def convert(a):
#     '''
#     converts a (oddly formatted) graph into an adjancency matrix
#     '''
#     adjList = defaultdict(set) 
#     for i in range(len(a)): 
#         for j in a[i]:
#             adjList[j].add(i)
#     return adjList

# visited = set() 
# '''
# initializes global var visited    
# '''

# def dftRecursive(start, graph, result):
#     visited.add(start)
#     for path in start:
#         if path not in visited:
#             dftRecursive(path, graph, result)  
#     result.append(visited)
    
# def csFindAllPathsFromAToB(graph):
#     result = []
#     aList = convert(graph)
#     start = aList[0]
#     dftRecursive(start, aList, result)
#     return result

def csFindAllPathsFromAToB(graph):
    stack = deque()        
    stack.append((0, [0])) #Starts stack with the starting node and no path
    res = []
    destinationNode = len(graph) - 1 #the index of the last element 
    while len(stack) > 0:
        curr = stack.pop() #rmoves/assigns most recent node added to curr
        currNode = curr[0] #assigns 1st element in node (value)
        currPath = curr[1] #assigns 2nd element in node (path) 
        for neighbor in graph[currNode]: #iterates over list of neighboring nodes
            newPath = currPath.copy()    # makes a copy of the path so additional 
            newPath.append(neighbor)     # neighbors can be added for each path
                                         # while not changing the path for the other 
                                         # neighbors... so [0,1,2] can become 
                                         # [0,1,2,3] or [0,1,2,4] for the next                              
                                         # iteration
            if neighbor == destinationNode: # when reaching the emd
                res.append(newPath)         #add path constructed to resulting array
            else:
                stack.append((neighbor, newPath)) # continue looping by pushing new
                                                  # path additions and neighbor
                                                  # value to the stack
    res.sort() 
    return res<jupyter_output><empty_output><jupyter_text>Mod 4  csFriendCircles

There are N students in a baking class together. Some of them are friends, while some are not friends. The students' friendship can be considered transitive. This means that if Ami is a direct friend of Bill, and Bill is a direct friend of Casey, Ami is an indirect friend of Casey. A friend circle is a group of students who are either direct or indirect friends.

Given a N*N matrix M representing the friend relationships between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not.

You need to write a function that can output the total number of friend circles among all the students.

Example 1:
Input: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
Output: 2
Explanation: The 0th and 1st students are direct friends, so they are in a friend circle. 
The 2nd student himself is in a friend circle. So return 2.


Input: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
Output: 2
Explanation: The 0th and 1st students are direct friends, so they are in a friend circle. 
The 2nd student himself is in a friend circle. So return 2.

Example 2:
Input: 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
Output: 1
Explanation: The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends, 
so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.
  working solution<jupyter_code>def adjList(matrix):
    cur = 0
    res = []
    adjList = []
    for i in range(len(matrix)):
        res.append([] * len(matrix))
        #creates indexes to fill later with values instead of 1's 
    while cur < len(matrix):
        for i in range(len(matrix[cur])):
            if matrix[cur][i] == 1:
                res[cur].append(i)
        cur += 1
    return res


def hlp(aList, n, visited, i):
    for x in aList:
      if x not in visited:
        visited.append(x)
        hlp(aList, n, visited, x)
  
    
def csFriendCircles(friendships):
    n = len(friendships)
    aList = adjList(friendships)
    visited = []
    res = 0  
    for i in range(n): # the outer loop ensures unconnected nodes get traversed
        if i not in visited:
            visited.append(i)
            hlp(aList, n, visited, i)
            res += 1
    return res
    
    #whew.. completed<jupyter_output><empty_output><jupyter_text>without conversion to adjList<jupyter_code>def hlp(friendships, visited, i):
    for x in range(len(friendships[i])):
      if x not in visited and friendships[i][x] == 1:
        visited.append(x)
        hlp(friendships, visited, x)
        
def csFriendCircles(friendships):
    n = len(friendships)
    visited = []
    res = 0  
    for i in range(n):
        if i not in visited:
            visited.append(i)
            hlp(friendships, visited, i)
            res += 1
    return res
sum([10, 5, 15])<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup