```class Tree(object):
def __init__(self, x, left=None, right=None):
self.value = x
self.left = left
self.right = right

x = Tree(1, Tree(0, Tree(1), Tree(3)), Tree(4))

def solution(t):
if not t:
return 0

stack = [(t, 0)]
branchesSum = 0

while stack:
node, v = stack.pop()
if node.left or node.right:
#depth first search
# the v is a little confusing to understand but easier to see in python tutor
# it goes from 1 to 10 to 100 etc. based on the height of the branch
# can probably do something like str() and converting back to int() as well
if node.left:
stack.append((node.left, node.value + v * 10))
if node.right:
stack.append((node.right, node.value + v * 10))
else:
branchesSum += node.value + v * 10
return branchesSum
```
```#
# Binary trees are already defined with this interface:
# class Tree(object):
#   def __init__(self, x):
#     self.value = x
#     self.left = None
#     self.right = None
import math
def solution(t):
if t is None: return []

stack = [t]
result = []

while len(stack) > 0:
result.append(max(tree.value for tree in stack))
next_row = [tree.left for tree in stack if tree.left] + [tree.right for tree in stack if tree.right]
stack = next_row
return result

#1. Add max value of ‘stack’ to result. 2. Create a new list of all next values for each value in stack. 3. redefine stack to this newly made list. 4. repeat

#alternate solution
def solution(t):
largestValues = []
q = []
height = 0
if t:
q.append([t, height])
while q:
item = q.pop()
node = item[0]
currentHeight = item[1]
if node.left:
q.insert(0, [node.left, currentHeight + 1] )
if node.right:
q.insert(0, [node.right, currentHeight + 1])
checkLargest(node.value, currentHeight, largestValues)

return largestValues

def checkLargest(value, height, largestValues):
if height == len(largestValues):
largestValues.append(value)
else:
if largestValues[height] < value:
largestValues[height] = value```
```class CircularQueue:
def __init__(self, size):
self.size = size
self.tail = 0
self.buffer = [None] * size
self.length = 0

def enqueue(self, value):
self.length += 1
self.buffer[self.tail] = value
self.tail += 1
if self.tail >= self.size:
self.tail = 0

def dequeue(self):
self.length -= 1
return value
```
```# //Tree Traversal (visit every node once)
# //Heavy on recursion

# //Breadth-first (BFS) vs. Depth-first (DFS)

# // DFS:
# // 1) in order (go in order of value)
# // 2) pre order (start at root)
# // 3) post order (start at botom)

# //When to use BFS vs. DFS:
# //For a fully loaded (wide) tree, BFS queue will be overloaded in the start (overloaded space complexity)
# //For a longer tree, DFS will take more memory (more rare, Trees are usually wide)
# //Big O for both is same

# //In order: useful if you want sorted array at end (you don't really know what the root is bc it's in the middle)
# //PreOrder: useful to "export a tree" so that it can be copied bc it flattens it

class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None

class BinarySearchTree:
def __init__(self):
self.root = None

def insert(self, value):
#creates new Node
new_node = Node(value)
#start at root
#if no root exists, root becomes new_node
if self.root == None:
self.root = new_node
return self

current = self.root

while True:
#to handle special case where value is same as current node
#you can return None or you can add a counter property
if value == current.value:
return None
#check to see if value is less than current
if value < current.value:
#check to see if there is node to left
#if not, add new_node to left
if current.left == None:
current.left = new_node
return self
#if there is node to left, move to that node and repeat
current = current.left
#check to see if value is greater than current
else:
#check to see if there is node to right
#if not, add new_node to right
if current.right == None:
current.right = new_node
return self
#if there is node to right, move to that node and repeat
current = current.right

#Breadth first search iterative using queue
def BFS(self):
node = self.root
#we will return data
data = []
queue = []
#place root node inside queue (recall FIFO)
queue.append(node)
#while queue is not empty
while len(queue) > 0:
#dequeue node from queue and append to data
node = queue.pop(0)
data.append(node)
#if there is left on node dequeued, add to queue
if node.left:
queue.append(node.left)
#if there is right on node dequeued, add to queue
if node.right:
queue.append(node.right)
#above two lines of code could be changed if it was a ternary tree, etc. instead of binary
#just loop for all children
return data

#parent down uses recursive
def DFSPreoder(self):
data = []
#if you want to DFS not from root, create a variable here named current and specify which node to start from
#helper function
def traverse(node):
#all of root node's left will happen first, then right
#for other types of DFS, just tweak this order
data.append(node.value)
if node.left:
traverse(node.left)
if node.right:
traverse(node.right)

traverse(self.root)
return data

#children up, root should be last value
def DFSPostOrder(self):
data = []

def traverse(node):
if node.left:
traverse(node.left)
if node.right:
traverse(node.right)
data.append(node.value)

traverse(self.root)
return data

#result data list should be sorted
def DFSInOrder(self):
data = []
def traverse(node):
if node.left:
traverse(node.left)
data.push(node.value)
if node.right:
traverse(node.right)
traverse(self.root)
return data

t = BinarySearchTree()
t.insert(1)
t.insert(5)
t.insert(6)
t.insert(2)
t.insert(0)
t.insert(-1)
t.insert(7)

print(t.DFSInOrder())```
```//Useful for background tasks, uploading resources, print/task

//Can be impleneted with array (use push/shift or unshift/pop) or queue class
//Again any time you use shift/unshift, you have O(N)
//FIFO

class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next

class Queue:
def __init__(self, first=None, last=None, size=0):
self.first = first
self.last = last
self.size = size

#add to end of queue (similar to append or push) and returns size
def enqueue(self, value):
new_node = Node(value)

if self.first == None:
self.first = new_node
self.last = new_node
else:
self.last.next = new_node
self.last = new_node

self.size += 1
return self.size

#remove from beginning of queue
def dequeue(self):
if self.first == None:
return None

temp = self.first
if self.first == self.last:
self.last = None
#set 1st property to be original first's next
self.first = self.first.next
self.size -= 1

return temp.value

#useful to visualize any other function works
def print_queue_to_list(self):
result = []
current = self.first
while current:
result.append(current.value)
current = current.next
print(result)

s = Queue()
s.enqueue(1)
s.enqueue(2)
s.enqueue(3)
s.print_queue_to_list() >> [1, 2, 3]
s.dequeue()
s.print_queue_to_list() >> [2, 3]

// Big O:
// Insertion and Removal: O(1) **this is mainly what stacks are good for
// Access and Search: O(N)
//Recall with array implenetation, insertion and removal is not constant ```
```# //Used in call stack, undo/redo, routing

# //Array implenentation (just use pop/push or shift/unshift)
# //Recall that pop/push is more efficient than shift/unshift
# //Indexes take up memory so linked list implenetation will be better

# //Single linked implenetation of stack:

class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next

class Stack:
def __init__(self, first=None, last=None, size=0):
self.first = first
self.last = last
self.size = size

#Similar to shift or insert(0, value). Adds to stack and returns size. Recall stack is LIFO
def push(self, value):
new_node = Node(value)
if self.first == None:
self.first = new_node
self.last = new_node
else:
#stores current 1st property on stack
temp = self.first
#reset 1st property to be newly created one
self.first = new_node
#set new next property
self.first.next = temp
#increment stack
self.size += 1
return self.size

#in python, this would be pop(0). Similar to unshift. Removes first element on stack
def pop(self):
#special case if stakc is empty
if self.first == None:
return None

temp = self.first
#if there is only 1 node, set 1st node and last property to be None
if self.first == self.last:
self.last = None
#self.first = None will be set in next line

#for all scenarios except empty stack
self.first = self.first.next
self.size -= 1
return temp.value

#useful to visualize reverse() or any other function works
def print_stack_to_list(self):
result = []
current = self.first
while current:
result.append(current.value)
current = current.next
print(result)

s = Stack()
s.push(1)
s.push(2)
s.push(3)
s.print_stack_to_list() # [3, 2, 1]
s.pop()
s.print_stack_to_list() #[2, 1]

# //these methods deal with 1st node bc thats what stacks do (LIFO)
# // Big O:
# // Insertion and Removal: O(1) **this is mainly what stacks are good for
# // Access and Search: O(N)
```
```# //almost identical to doubly linked list but
# //every node has another pointer to previous node
# //Advantages: able to access list at end instead of going from start
# //Disadvantages: takes up more memory

class Node:
def __init__(self, value, next=None, previous=None):
self.value = value
self.next = next
self.previous = previous

self.tail = tail
self.length = length

def append(self, value):
new_node = Node(value)
#if there is no head (list is empty), set head and tail to be new_node
self.tail = new_node
#otheriwse, set next property on tail to be new node and set tail to be newly created node
else:
self.tail.next = new_node
new_node.previous = self.tail
self.tail = new_node
#increment length and return
self.length += 1
return self

#removes last element of list
def pop(self):
return None
#current will eventually be the last elemeent and will be removed
#variable right before end
new_tail = current
#while loop to traverse to end
while current.next:
new_tail = current
current = current.next
#sets new tail
self.tail = new_tail
#cuts off old tail and current previous property
self.tail.next = None
current.previous = None
#decrement list
self.length -= 1
#to account when list will be destroyed
if self.length == 0:
self.tail = None
return current

#removes elememnt at head. Note in python, shift doesn't exist, it would be .pop(0) or you can use remove which is defined later
def shift(self):
return None
#current_head will be removed and returned
self.length -= 1
#to account when list will be destroyed
if self.length == 0:
self.tail = None

#adds to start of list and replaces head. I included shift/unshift because this is what makes linked list special in terms of reducing big O
def unshift(self, value):
new_node = Node(value)
#edge case to account if list is originally empty
else:
self.length += 1

#travels to node at index and returns node
def traverse(self, index):
if index < 0 or index >= self.length:
raise IndexError('index out of range')
counter = 0
#since this is doubly linked list, you can also approach from tail and go backwards
while counter != index:
current = current.next
counter += 1
return current

#travels to node at index and returns node's value
def get(self, index):
#to accomodate normal python function, where if you give index = -1 in a get(), it will return last index and so on
if index < 0:
index = self.length + index
node = self.traverse(index)
return node.value

#replaces value at index
def set(self, index, value):
found_node = self.traverse(index)
if found_node:
found_node.value = value
return True
else:
return False

#insert value at index and adds 1 to length, returns boolean if successful
def insert(self, index, value):
if index < 0 or index > self.length:
raise IndexError('index out of range')
if index == self.length:
#not not is similar to !! in javascript and it's so it returns a boolean if successful
return not not self.append(value)
if index == 0:
return not not self.unshift(value)
else:
new_node = Node(value)
previous_node = self.traverse(index - 1)
after_node = previous_node.next

#creating relations before new_node
previous_node.next = new_node
new_node.previous = previous_node
#creating relations after new_node
new_node.next = after_node
after_node.previous = new_node

#increment length
self.length += 1
return self

def remove(self, index):
if index < 0 or index > self.length:
return indexError('index out of range')
if index == self.length - 1:
return self.pop()
if index == 0:
return self.shift()
else:
#need to get previous node and after node to create relationships
previous_node = self.traverse(index - 1)
#removed_node will be removed and returned
removed_node = previous_node.next
after_node = removed_node.next
previous_node.next = removed_node.next
after_node.previous = previous_node
#sever removed_node next
removed_node.next = None
removed_node.previous = None
self.length -= 1
return removed_node

#common interview question
def reverse(self):
self.tail = current

next, previous = None, None
#to show for loop is possible in LL. Could use while loop as well
for i in range(0, self.length):
#think of this as creating the block
next = current.next
current.next = previous #initially None
current.previous = next
#think of this as connecting head/previous to the block
previous = current
current = next
return self

# # // [100. 201, 250, 350, 999]
# # // first part
# # // NODE  NEXT
# # // 100 -> null

# # // second part (for loop and beyond)
# # // PREV  NODE  NEXT
# # // line 154( prev = current; ) specifically:
# # // 201 -> 100  -> null
# # // line 155 (current = next;):
# # //        PREV  NODE  NEXT
# # // 250 -> 201 -> 100

#useful to visualize reverse() or any other function works
result = []
while current:
result.append(current.value)
current = current.next
print(result)

# l.append(1)
# l.append(2)
# l.pop()
# l.shift()
# l.unshift(3)
# l.append(4)
# l.traverse(0)
# l.get(-2)
# l.set(2, 7)
# l.insert(0, 99)
# l.remove(2)
# l.reverse()

# y = l.length
# print(y)

# // Insertion:
# // O(1)
# // Removal: recall in SL it depends
# // O(1)
# // Searching:
# // O(N) but optimized bc you can start from head or tail (but more memory)
# // Access:
# // Same as searching ```
```class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next

self.tail = tail
self.length = length

def append(self, value):
new_node = Node(value)
#if there is no head (list is empty), set head and tail to be new_node
#otheriwse, set next property on tail to be new node and set tail to be newly created node
else:
self.tail.next = new_node
self.tail = self.tail.next
#increment length and return
self.length += 1
return self

#removes last element of list
def pop(self):
return None
#current will eventually be the last elemeent and will be removed
#variable right before end
new_tail = current
#while loop to traverse to end
while current.next:
new_tail = current
current = current.next
#sets new tail
self.tail = new_tail
#cuts off old tail
self.tail.next = None
#decrement list
self.length -= 1
#to account when list will be destroyed
if self.length == 0:
self.tail = None
return current

#removes elememnt at head. Note in python, shift doesn't exist, it would be .pop(0) or you can use remove which is defined later
def shift(self):
return None
self.length -= 1
#to account when list will be destroyed
if self.length == 0:
self.tail = None

#adds to start of list and replaces head. I included shift/unshift because this is what makes linked list special in terms of reducing big O
def unshift(self, value):
new_node = Node(value)
#edge case to account if list is originally empty
else:
self.length += 1

#travels to node at index and returns node
def traverse(self, index):
if index < 0 or index >= self.length:
raise IndexError('index out of range')
counter = 0
while counter != index:
current = current.next
counter += 1
return current

#travels to node at index and returns node's value
def get(self, index):
#to accomodate normal python function, where if you give index = -1 in a get(), it will return last index and so on
if index < 0:
index = self.length + index
node = self.traverse(index)
return node.value

#replaces value at index
def set(self, index, value):
found_node = self.traverse(index)
if found_node:
found_node.value = value
return True
else:
return False

#insert value at index and adds 1 to length, returns boolean if successful
def insert(self, index, value):
if index < 0 or index > self.length:
raise IndexError('index out of range')
if index == self.length:
#not not is similar to !! in javascript and it's so it returns a boolean if successful
return not not self.append(value)
if index == 0:
return not not self.unshift(value)
else:
new_node = Node(value)
previous_node = self.traverse(index - 1)
temp = previous_node.next
#set next property of previous node to be new_node
previous_node.next = new_node
#set new_node next to be old next of previous
#you can also write this as previous_node.next.next = temp
new_node.next = temp
self.length += 1
return True

def remove(self, index):
if index < 0 or index > self.length:
return indexError('index out of range')
if index == self.length - 1:
return self.pop()
if index == 0:
return self.shift()
else:
#need to get previous node to create relationships
previous_node = self.traverse(index - 1)
#removed_node will be removed and returned
removed_node = previous_node.next
previous_node.next = removed_node.next
#sever removed_node next
removed_node.next = None
self.length -= 1
return removed_node

#common interview question
def reverse(self):
self.tail = current

next, previous = None, None
#to show for loop is possible in LL. Could use while loop as well
for i in range(0, self.length):
#think of this as creating the block
next = current.next
current.next = previous #initially None
#think of this as connecting head/previous to the block
previous = current
current = next
return self

# // [100. 201, 250, 350, 999]
# // first part
# // NODE  NEXT
# // 100 -> null

# // second part (for loop and beyond)
# // PREV  NODE  NEXT
# // line 154( prev = current; ) specifically:
# // 201 -> 100  -> null
# // line 155 (current = next;):
# //        PREV  NODE  NEXT
# // 250 -> 201 -> 100

#useful to visualize reverse() works
result = []
while current:
result.append(current.value)
current = current.next
print(result)

l.push(1)
l.push(2)
l.pop()
l.shift()
l.unshift(3)
l.push(4)
l.traverse(0)
l.get(-2)
l.set(2, 7)
l.insert(0, 99)
l.remove(2)
l.reverse()

y = l.length
print(y)

# //Big O:
# //Insertion: O(1)
# //Removal: depends O(1) if start or O(N) at end
# //Above 2 are main advantages vs. arrays esp at start
# //Searching: O(N)
# //Access: O(N)

# //Recall with array implenetation, insertion and removal is not constant ```
```# //Lists are linear but trees are nonlinear
# //Often working with binary trees and specifically binary search trees

# //SL is techically a special case tree

# //Root: top node of tree
# //Child: node directly connected to another node when moving away from root
# //Parent: converse notion of child
# //Siblings: group of node with same parent
# //Leaf: node with no children
# //Edge: connection betweeen one node and another (often arrows)

# //Used for HTML DOM, network routing, abstract syntax trees, folder organization, AI, best possible move (decision tree)

# //We will focus on binary search tree (can only have at most 2 child nodes)
# //For each node, everything to left is smaller. Right >> bigger

class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None

class BinarySearchTree:
def __init__(self):
self.root = None

def insert(self, value):
#creates new Node
new_node = Node(value)
#start at root
#if no root exists, root becomes new_node
if self.root == None:
self.root = new_node
return self

current = self.root

while True:
#to handle special case where value is same as current node
#you can return None or you can add a counter property
if value == current.value:
return None
#check to see if value is less than current
if value < current.value:
#check to see if there is node to left
#if not, add new_node to left
if current.left == None:
current.left = new_node
return self
#if there is node to left, move to that node and repeat
current = current.left
#check to see if value is greater than current
else:
#check to see if there is node to right
#if not, add new_node to right
if current.right == None:
current.right = new_node
return self
#if there is node to right, move to that node and repeat
current = current.right

#find() returns value while contains() returns boolean
#find will point to entire node
def find(self, value):
#check to see if there is root and if not, we are done!
if self.root == None:
return False
current = self.root
found = False

#if value is less than current
if value < current.value:
#check to see if there is node to left
#if there is, move to that node and repeat
current = current.left
#if not, we ar edone because current will no longer exist
#if value is greater than current
elif value > current.value:
#check to see if there is node to right
#if there is, move to that node and repeat
current = current.right
#if not, we are done because current will no longer exist
else:
found = True

return None
return current

def contains(self, value):
if self.root == None:
return False
current = self.root
found = False

if value < current.value:
current = current.left
elif value > current.value:
current = current.right
else:
return True
return False

t = BinarySearchTree()
t.insert(3)
t.insert(5)
t.insert(2)
t.insert(-1)
t.insert(6)
t.find(6)
t.contains(6)

# // Insertion and Search: O(log N) VERY GOOD
# // Not guaranteed if BST is a one sided tree (choose a different root)

# //      10
# //   5     13
# // 2  7  11  16

# // tree = BinarySearchTree()
# // tree.insert(10)
# // tree.insert(5)
# // tree.insert(13)
# // tree.insert(11)
# // tree.insert(2)
# // tree.insert(16)
# // tree.insert(7)
# // tree.find(7) >> will point to node with 7
# // tree.contains(6) >> False

# //Primitive way of making Tree before insert()
# // tree = BinarySearchTree()
# // tree.root = Node(10)
# // tree.root.right = Node(15)
# // tree.root.left = Node(7)
# // tree.root.left.right = Node(9)

```