# Trees

```# 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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if not p and not q: return True
if not p or not q: return False
if p.val != q.val: return False

return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
```
```# 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 isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
#order of first two conditionals is important
if not subRoot: return True
if not root: return False
if self.sameTree(root, subRoot): return True

return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

def sameTree(self, s, t):
if not s and not t: return True
if s and t and s.val == t.val:
return self.sameTree(s.left, t.left) and self.sameTree(s.right, t.right)

return False

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

tx = Tree(4, Tree(1, Tree(-2, None, Tree(3, None, None))), Tree(3, Tree(1, None, None), Tree(2, Tree(-4, None, None), Tree(-3, None, None))))

def find_paths(root, required_sum):
allPaths = []

def find_paths_recursive(currentNode, required_sum, currentPath, allPaths):
if currentNode is None:
return

# add the current node to the path
currentPath.append(currentNode.val)

# if the current node is a leaf and its value is equal to required_sum, save the current path
if currentNode.val == required_sum and currentNode.left is None and currentNode.right is None:
allPaths.append(list(currentPath))
else:
# traverse the left sub-tree
find_paths_recursive(currentNode.left, required_sum -
currentNode.val, currentPath, allPaths)
# traverse the right sub-tree
find_paths_recursive(currentNode.right, required_sum -
currentNode.val, currentPath, allPaths)

# remove the current node from the path to backtrack,
# we need to remove the current node while we are going up the recursive call stack.
del currentPath[-1]

find_paths_recursive(root, required_sum, [], allPaths)

return allPaths

find_paths(tx, 5)```
```#
# 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 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
```
```class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
subset = []
result = []

#i is index of subset
def dfs(i):
if i >= len(nums):
result.append(subset.copy())
return

#decision to include nums[i]
subset.append(nums[i])
#this recursive call will be given filled subset
dfs(i + 1)

#decision NOT to include nums[i]
subset.pop()
#this recursive call will be given empty subset
dfs(i + 1)

dfs(0)

return result

```
```class Solution:

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
result = []

#i is index of candidates
def dfs(i, current, total):
if total == target:
#if you do not add .copu() it will append empty arrays
result.append(current.copy())
return
if i >= len(candidates) or total > target:
return

#decision tree has 2 options: 1) add candidates[i] or 2) do not add and move on to next index