Leetcode: Trees

Question 1

strategies for trees

Answer 1

1. linear searching doesn’t work since the array representing a tree isn’t linear
2. recursion is great to solve these because each node is itself a subtree, so it will be evaluated the same way
3. remember to always have a good base case
4. call the left tree, right tree, and merge the results!

https://www.youtube.com/watch?v=s2Yyk3qdy3o&t=140s

Question 2

Same Tree

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Answer 2

1. search through with any of the traversals, postorder, inorder, preorder, preorder is easiest in my experience
2. every time you see a problem similar to a basic scenario, there is ALWAYS a twist to it. With sort 3 nums, it was binary search with the “==” performing a different function, for this one it is the None nodes. If both the nodes are none, that is fine! if one is and the other isn’t it is bad
3. this is a tree problem, so recursion is usually the easiest way to go about it since each recursive call is also a tree and will be evaluated the same

time: O(min(n, m)), it would be the min because worst case the smallest one will fail and we end the search
space: O(n+m), best case it would be log(n) since the tree would be balanced. worst case is we traverse each tree fully

class Solution:

• —def recursion(self, p, q):
• ——-if not p and not q:
• ———–return True
• ——-elif not p or not q:
• ———–return False
• ——-if p.val==q.val:
• ———–if self.recursion(p.left, q.left) and self.recursion(p.right, q.right):
• —————return True
• ———–else:
• —————return False
• ——-else:
• ———–return False
• —def isSameTree(self, p, q) -> bool:
• ——-if not p and not q:
• ———–return True
• ——-elif not p or not q:
• ———–return False
• ——-stack1=[p]
• ——-stack2=[q]
• ——-while stack1 and stack2:
• ———–node1 = stack1.pop()
• ———–node2 = stack2.pop()
• ———–if node1.val==node2.val:
• —————if node1.right and node2.right:
• ——————-stack1.append(node1.right)
• ——————-stack2.append(node2.right)
• —————elif not node1.right and not node2.right:
• ——————-pass
• —————else:
• ——————-return False
• —————if node1.left and node2.left:
• ——————-stack1.append(node1.left)
• ——————-stack2.append(node2.left)
• —————elif not node1.left and not node2.left:
• ——————-pass
• —————else:
• ——————-return False
• ———–else:
• —————return False
• ——-return True

Question 3

invert a binary tree

Answer 3

class Solution:

• —def invertTree(self, root):
• ——-if not root:
• ———–return root
• ——-stack=[root]
• ——-while stack:
• ———–node = stack.pop()
• ———–node.right, node.left = node.left, node.right
• ———–if node.left : stack.append(node.left)
• ———–if node.right : stack.append(node.right)
• ——-return root
• —def recursive(self, root):
• ——-if root:
• ———–root.left, root.right = root.right, root.left
• ———–self.recursive(root.left)
• ———–self.recursive(root.right)
• ——-return root

Question 4

calculate height of a binary tree, height of an n-ary tree

Answer 4

1. start with if node is null, which will give 0
2. then if node only has a root, that gives 1
3. figure out recursively from there

binary tree

• —def height(self, node):
• ——-if not node:
• ———–return 0
• ——-rh = self.height(node.right)
• ——-lh = self.height(node.left)
• ——-return max(rh+1, lh+1)

1. Think BFS
   - —def iterative(self, root) -> int:
   - ——-if not root:
   - ———–return 0
   - ——-li=[root]
   - ——-c=0
   - ——-while li:
   - ———–x=len(li)
   - ———–for i in range(x-1, -1, -1):
   - —————cur=li.pop(0)
   - —————if cur.left:
   - ——————-li.append(cur.left)
   - —————if cur.right:
   - ——————-li.append(cur.right)
   - ——-return c

n-ary

• —def get_depth(self, node):
• ——-if not node:
• ———–return 0
• ——-m=0
• ——-for n in node.children:
• ———–d=self.get_depth(n)
• ———–m=max(m,d)
• ——-return m+1

Question 5

Unique Binary Search Trees

Given an integer n, return the number of structurally unique BST’s (binary search trees) which has exactly n nodes of unique values from 1 to n.

Answer 5

1. break it down into smaller problems, think tree based problems
2. n=3, we have 5 ways to make trees, we need to enumerate from 1,3+1, and see that all i-1 is on the left of root n and n-i
3. if there are 2 options on the left, 2 on the right, then we have 4 total combinations
4. add that to a sum, return the sum using sub-recursion (i made this up it’s when you use a recursive function but only have 1 return statement like below, each conditional doesn’t have a return)
5. if you somehow figured that out, then realize that each value of n can be memoized. create a map, initialize it with 0=1, 1=1 bc if we get 0 then we will return 0 since 0*an=0.
6. add values to the map as soon as you get the final sum for that n.
7. check if n in map each time

BONUS: this is a Catalan number, meaning that C0=1, and Cn+1 = (2(2n+1)/(n+2) * Cn
so you can just do that too, loop from 0,n since catalan numbers start at index 0

time: memoized it is O(n), else it is 2^n exponential, each n spawns 2 more of itself
space: linear, o(n), size of map

class Solution:

• —def numTrees(self, n: int) -> int:
• ——-m={0:1, 1:1}
• ——-return self.helper(n, m)
• —def helper(self, n, m):
• ——-if n in m:
• ———–return m[n]
• ——-s = 0
• ——-for i in range(1, n+1):
• ———–s+=self.helper(i-1, m) * self.helper(n-i, m)
• ——-m[n]=s
• ——-return s

1. same idea as above, except instead of memoizing we us a dp array
2. remember the previous base case, 0 and 1 return 1, so we need to start there. The same idea using j-1 and = i-j

• —def dynamic_programming(self, n):
• ——-G = [0]*(n+1)
• ——-G[0], G[1] = 1, 1
• ——-for i in range(2, n+1):
• ———–for j in range(1, i+1):
• —————G[i] += G[j-1] * G[i-j]
• ——-return G[n]

Question 6

Unique Binary Search Trees 2

Given an integer n, return all the structurally unique BST’s (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
Example 2:

Input: n = 1
Output: [[1]]

Answer 6

Understand the first problem! write it out on paper to really understand how this makes sense. know bst are catalan numbers: C0=1, C n+1 = (2*(2n+1))/(n+2)) * Cn

1. given the root i, the left roots are equal to i-1, and the right are equal to n-i
2. how to replicate this here for each node? given an i, we need to return all of the left/right nodes in a list format
3. the hard part here is realizing that the method signature includes the (start, end) to give the range, and what a base case looks like, so we need a helper method
4. base case is if start > end, return [None], when start==end that is okay (think n=1, (1,1))
5. next what do we put in each method signature, how do we calculate it for left /right?
6. (1,3), left has no values when i=1, i=2 we have 1 value, which is Node(1). thinking recursively, we want to pass in values that gives us the result of passing in n=1. reverse engineering this, left=helper(start, i-1)
7. for right, (1,3) i=1, right will have Node 2 and 3, we want to give the method values that has the same number of combinations as n=2, but ends at our input n. this gives us helper(i+1, n) which is (2,3) in this case
8. at each i, we return a list of left/right, we do a double for loop through both, creating nodes at i with left/right equally the value in left/right. This is similar to in the first problem how we did s+=helper(i-1)*helper(n-i), we are basically giving 1 combination of the right node, then combining it with each combination on the left. we do this for all the left/right nodes

time: Catalan number time complexity is O(4^n / n^1/2). this is because Catalan numbers grow as n* Gn (Gn is catalan at n), n* Gn = O(4^n / n^1/2)
space: n* Gn = O(4^n / n^1/2), n=3 it is 35, n=4 is 414, think of the response node and how big it will be, the space is equal to the time complexity since each iteration adds 1 to the list

time if you dont know catalan: If you have a tree with branching of b and max depth of m, the total number of nodes in this tree in worst case: 1 + b + b^2 + … + b^(m-1), which is a sum of geometric sequence: (b^m-1)/(b-1). So you can say that time complexity is O(b^m). For the example above it will be O(n*2^n). It is not exact as a Catalan number but I think it is enough in an interview.

class Solution:

• —def generateTrees(self, n: int):
• ——-return self.helper(1, n)
• —def helper(self, start, end):
• ——-if start>end:
• ———–return [None]
• ——-response=[]
• ——-for i in range(start, end+1):
• ———–left = self.helper(start, i-1)
• ———–right = self.helper(i+1, end)
• ———–for r in right:
• —————for l in left:
• ——————-c = TreeNode(i)
• ——————-c.right=r
• ——————-c.left=l
• ——————-response.append(c)
• ——-return response

Question 7

validate a binary search tree

Answer 7

1. get a base case, apply conditions to both nodes, repeat on each node
2. the starter code is not enough, we need to keep track of the lowest/highest values we can be between
3. create a helper method with default low/high, check root value is less/greater than them, recursively call the helper on each node.
4. most important thing is to recognize if you do root.left.val, root.left could be null, and it is very hard to work around null checking and value checking. YOU ARE THE MASTER OF THE CODE! don’t let something like this stall you, YOU can make a workaround

time: O(n), linear, we search through each node
space: O(n), linear, the recursive calls on the stack will be equal to the number of nodes

class Solution:
----def answer(self, node, _min=float("-inf"), _max=float("inf")):
--------if not node:
------------return True
--------val = node.value
if val is less than mid and greater than max,
----return true
default return false

Question 8

postorder traversal

Answer 8

post order, meaning post fact, reverse the preorder!
Left, right, root

• —def postorder(self, node):
• ——-if node:
• ———–self.post_order(node.left)
• ———–self.post_order(node.right)
• ———–print(node.value, end=””)

1. unsure how to do this one? update later

• —def postorder_iterative(self, node):
• ——-if not Node:
• ———–return
• ——-s1 = []
• ——-s2 = []
• ——-s1.append(node)
• ——-while s1:
• ———–current = s1.pop()
• ———–s2.append(current)
• ———–if current.left: s1.append(current.left)
• ———–if current.right: s1.append(current.right)
• ——-while s2:
• ———–node2 = s2.pop()
• ———–print(node2.value, end=””)
• —def postorder_hard(self, node):
• ——-if not node:
• ———–return
• ——-stack=[]
• ——-while True:
• ———–while node:
• —————if node.right:
• ——————-stack.append(node.right)
• —————stack.append(node)
• —————node = node.left
• ———–node = stack.pop()
• ———–if node.right and self.peek(stack)==node.right:
• —————stack.pop()
• —————stack.append(node)
• —————node=node.right
• ———–else:
• —————print(node.value)
• —————node=None

Question 9

inorder traversal

Answer 9

INorder, INFINITE, WHILE TRUE:
left, root, right

• —def inorder(self, node):
• ——-if node:
• ———–self.in_order(node.left)
• ———–print(node.value, end=””)
• ———–self.in_order(node.right)
• —def inorder_iterative(self, node):
• ——-stack = []
• ——-current = node
• ——-while True:
• ———–if current:
• —————stack.append(current)
• —————current = current.left
• ———–elif stack:
• —————current = stack.pop()
• —————print(current.value, end=””)
• —————current = current.right
• ———–else:
• —————break

Question 10

preorder traversal

Answer 10

root, left, right

• —def preorder(self, node):
• ——-if node:
• ———–print(node.value, end=””)
• ———–self.preorder(node.left)
• ———–self.preorder(node.right)
• —def preorder_iterative(self, node):
• ——-stack=[]
• ——-stack.append(node)
• ——-while stack:
• ———–current = stack.pop()
• ———–if current:
• —————print(current.value)
• —————stack.append(current.right)
• —————stack.append(current.left)

Question 11

binary tree level order traversal, return each level as a list

return list[list[int]]

Answer 11

1. need to take a snapshot of the stack to understand how many items you want to reverse pop (pop(0)) off the stack/queue.

time: O(n), length of the binary tree
space: N length of output value and the stack would be O(D) where D is the diameter of the tree (largest length of a level)

• —def levelOrder(self, root):
• ——-if not root:
• ———–return
• ——-output=[]
• ——-stack=[root]
• ——-while stack:
• ———–n=len(stack)
• ———–li=[]
• ———–for i in range(n):
• —————cur=stack.pop(0)
• —————if cur.left:
• ——————-stack.append(cur.left)
• —————if cur.right:
• ——————-stack.append(cur.right)
• —————li.append(cur.val)
• ———–output.append(li)
• ——-return output

1. find depth, create the output accordingly, then append to the output based on the level
2. BONUS don’t need to know depth
3. each time you call helper, check the length of output vs level, if they are equal add another level to it
4. NEVER append a null value, or it will mess with the length(output list)=level calculation, this is the only way to do this recursively without calculating the depth. Once you see it, it makes sense, since len(empty list)==0, so we know we need to append it the first time, then once we go to the next level we add another
5. If we are on level 2, then len(list)==3, so the level is technically always 1 behind the length

• —def recursive(self, root):
• ——-output=[]
• ——-if not root:
• ———–return output
• ——-self.helper(root, 0, output)
• ——-return output
• —def helper(self, root, level, output):
• ——-if len(output)==level:
• ———–output.append([])
• ——-output[level].append(root.val)
• ——-if root.left:
• ———–self.helper(root.left, level+1, output)
• ——-if root.right:
• ———–self.helper(root.right, level+1, output)
• —def my_custom_one(self, root):
• ——-if not root:
• ———–return []
• ——-depth=self.depth(root)
• ——-output = [[] for i in range(depth)]
• ——-self.helper(root, 0, output)
• ——-return output
• —def custom_helper(self, root, level, output):
• ——-if not root:
• ———–return
• ——-output[level].append(root.val)
• ——-if root.left:
• ———–self.custom_helper(root.left, level+1, output)
• ——-if root.right:
• ———–self.custom_helper(root.right, level+1, output)
• —def depth(self, root):
• ——-if not root:
• ———–return 0
• ——-return 1+max(self.depth(root.left), self.depth(root.right))

Question 12

right view of binary tree

print the right view of the binary tree

Answer 12

1. level order
2. recursive level order, understand len(output)==level is the primary way to handle the recursion
3. len(empty list) is 0, we have level 0, meaning root so we just add it. then we increase the level to 1, we know that the len(levels) is always 1 behind the levels. Then when we traverse to a new level they are equal and we can add it!
4. for the sentinel, need to realize the sentinel node is a node we can use to signify a new level (adding a null node instead of tracking levels)
5. sentinel problem must check if queue is None before adding the None

time: O(n), we have to see all the nodes in most cases
space: O(D) where D is the diameter of the node, on a balanced tree it would be N/2. O(D) space bc we have to hold each level in the array at a time, which is the diameter

class Solution:

• —def two_queues(self, root):
• ——-if not root:
• ———–return []
• ——-output=[]
• ——-queue=[root]
• ——-while queue:
• ———–li=[]
• ———–for i in range(len(queue)):
• —————current=queue.pop(0)
• —————li.append(current)
• —————if current.left:
• ——————-queue.append(current.left)
• —————if current.right:
• ——————-queue.append(current.right)
• ———–output.append(li.pop().val)
• ——-return output

time: O(n), we have to see all the nodes in most cases
space: O(H) where H is the height of the tree since the recursive stack will not go further than the height

• —def recursive(self, root):
• ———–if not root:
• —————return []
• ———–output=[]
• ———–self.helper(root, output, 0)
• ———–return output
• —def helper(self, root, output, level):
• ——-if len(output) is level:
• ———–output.append(root.val)
• ——-if root.right:
• ———–self.helper(root.right, output, level+1)
• ——-if root.left:
• ———–self.helper(root.left, output, level+1)

time: O(n), we have to see all the nodes in most cases
space: O(D) where D is the diameter of the node, on a balanced tree it would be N/2

• —def sentinel_node(self, root):
• ——-if not root:
• —————return []
• ——-output=[]
• ——-queue=[root, None]
• ——-c=root
• ——-while queue:
• ———–prev, c=c, queue.pop(0)
• ———–while c:
• —————if c.left:
• ——————-queue.append(c.left)
• —————if c.right:
• ——————-queue.append(c.right)————
• —————prev, c = c, queue.pop(0)
• ———–output.append(prev.val)
• ———–if queue:
• —————queue.append(None)
• ——-return output

Question 13

Largest Smaller BST Key

Given a root of a Binary Search Tree (BST) and a number num, implement an efficient function findLargestSmallerKey that finds the largest key in the tree that is smaller than num. If such a number doesn’t exist, return -1. Assume that all keys in the tree are nonnegative.

Analyze the time and space complexities of your solution.

For example:

For num = 17 and the binary search tree below:

Answer 13

brute force is to do a BST for a key which is num-1 and make output= max(previous, current). Or each time you find a new number that meets the condition, do the same

1. realize you NEVER need to compare to previous value, in a BST, the num on the right is ALWAYS LARGER
2. each time we meet the condition, set the output and move right. if right meets it too, it is by definition larger than what we just had

time: O(n) at worst, best log(N) if we have a balanced tree
space: recursion stack is O(n) or log(n) at best

def find_largest_smaller_key(self, num):
----return self.helper(num, self.root, -1)

def helper(self, num, current, output):

• —if not current:
• — return output
• —else:
• — if current.key [less than] num:
• ——-# output = current.key
• ——-return self.helper(num, current.right, current.key)
• — else:
• ——-return self.helper(num, current.left, output)def iterative(self, num):
• —current = self.root
• —output=-1
• —while current:
• — if current.key [less than] num:
• ——-output=current.key
• ——-current = current.right
• — else:
• ——-current = current.left
• —return output

Question 14

merge two binary trees

You are given two binary trees root1 and root2.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Return the merged tree.

Note: The merging process must start from the root nodes of both trees.

Answer 14

1. binary tree, perform action on root node, copy for left and right.
2. remember, when comparing or operating on 2 trees, if 1 of the trees has finished its branch, you can return the other tree and be done (even if it is None, then both are None!)
3. iterative you need to choose which root you will return, then do null checks appropriately

time: O(min(n, m)), since if root1 is large and root2 is one node, after we merge the first node we will return the remainder of the list
space: O(min(n, m)) bc of the recursive stack or iterative stack. Best case is log(n).

class Solution:

• —def mergeTrees(self, root1, root2):
• ——-if not root1:
• ———–return root2
• ——-elif not root2:
• ———–return root1
• ——-root1.val += root2.val
• ——-root1.left = self.mergeTrees(root1.left, root2.left)
• ——-root1.right = self.mergeTrees(root1.right, root2.right)
• ——-return root1
• —def iteartive(self, root1, root2):
• ——-if not root1:
• ———–return root2
• ——-elif not root2:
• ———–return root1
• ——-stack1 = deque([root1])
• ——-stack2 = deque([root2])
• ——-while stack1 or stack2:
• ———–c1 = stack1.popleft()
• ———–c2 = stack2.popleft()
• ———–if not c2:
• —————continue
• ———–c1.val = c1.val + c2.val
• ———–if not c1.left:
• —————c1.left = c2.left
• ———–else:
• —————stack1.append(c1.left)
• —————stack2.append(c2.left)
• ———–if not c1.right:
• —————c1.right = c2.right
• ———–else:
• —————stack1.append(c1.right)
• —————stack2.append(c2.right)

——–return root1

Question 15

level order of an n-ary tree

Answer 15

easy solution is iterative BFS, which is O(n) time and space, the space is because of the response and in the worst case, a perfect tree’s base level with have n//2 nodes, which means the level array is equal to N space in those cases

1. recursive BFS means that you need to keep track of the level
2. if you are at a new level and it has not been added to the response, check, and add it
3. otherwise, just add it to the level already on the response

time: O(n), linear bc we see all the nodes
space: O(log(n)) best case if it is a perfect tree since recursion only goes down the height of the tree, worst case is O(n)

class Solution:

• —def recursive(self, root):
• ——-if not root:
• ———–return root
• ——-self.response = []
• ——-self.recursion(root, 0)
• ——-return self.response
• —def recursion(self, root, level):
• ——-if not root:
• ———–return
• ——-if len(self.response) [less than]= level:
• ———–self.response.append([])
• ——-self.response[level].append(root.val)
• ——-for child in root.children:
• ———–self.recursion(child, level + 1)
• —def iterative(self, root):
• ——-if not root:
• ———–return root
• ——-queue = [root]
• ——-response = []
• ——-while queue:
• ———–level = []
• ———–for i in range(size):
• —————current = queue.pop(0)
• —————level.append(current.val)
• —————for child in current.children:
• ——————-queue.append(child)
• ———–response.append(level)
• ——-return response

Question 16

You are given a binary tree in which each node contains an integer value. The integer value can be positive or negative.

Write a function that counts the number of paths in the binary tree that sum to a given value (the value will be provided as a function parameter).

The path does not need to start or end at the root or a leaf, but it must only go downwards.

Answer 16

brute is to do a preorder traversal at each node assuming it is the root, then calculate if you find the value, this is n^2 time and N space, or log(n) if it is a balanced tree

1. key is to know what a prefix sum is, then use that!

time: O(n), we traverse the tree once
space: O(n), recursive stack and the prefix sum map. both are linear, the recursive stack could be log(n) if balanced tree

class Solution:

• —def prefix_sum(self, root, targetSum):
• ——-if not root:
• ———–return 0
• ——-self.target = targetSum
• ——-self.carry = self.count = 0
• ——-self.prefix_sum = defaultdict(int)
• ——-self.pre_order(root)
• ——-return self.count
• —def pre_order(self, root):
• ——-self.carry += root.val
• ——-if self.carry == self.target:
• ———–self.count += 1

——–self.count += self.prefix_sum[self.carry - self.target]

——–self.prefix_sum[self.carry] += 1

——–if root.left:
————self.pre_order(root.left)
——–if root.right:
————self.pre_order(root.right)
# if we make carry a local method variable, then we do not have to do self.carry -= root.val, this is only necessary bc it is global so once it hits the end of the tree we need to do some backtracking
# We will always need to adjust the prefix sum, however
——–self.prefix_sum[self.carry] -= 1
——–self.carry -= root.val

1. I believe the time/space is O(2n) / O(2N) bc we loop through the tree twice at each node, then we have to check to make sure the node has not been seen before, it is hasn’t we can call it with a 0 carry, else we skip that

• —def bad(self, root, targetSum):
• ——-if not root:
• ———–return 0
• ——-self.seen = {}
• ——-self.count = 0
• ——-self.target = targetSum
• ——-self.path_helper(root, 0)
• ——-return self.count
• —def path_helper(self, root, carry):
• ——-if root.val + carry == self.target:
• ———–self.count += 1
• ——-if root.left:
• ———–if root.left not in self.seen:
• —————self.path_helper(root.left, 0)
• ———–self.path_helper(root.left, carry + root.val)
• —————self.path_helper(root.right, 0)
• ———–self.path_helper(root.right, carry + root.val)
• ——-self.seen[root] = True

Question 17

balanced binary tree (height balanced)

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: true

Answer 17

1. calculate height but with a twist!
2. each recursive call has the chance to nullify the balanced tree, check each time that rh - lh < 2
3. you can have the function return bool, height = if it is still valid + height, or if you find it is invalid, return infinity
4. check if previous values are infinity, if so, game return false

time: O(n), we have to check each node in the tree
space: O(n), could be logN if the tree is perfectly balanced

class Solution:

• —def isBalanced(self, root: Node) -> bool:
• ——-if not root:
• ———–return True
• ——-rh = self.height(root.right)
• ——-lh = self.height(root.left)
• ——-if rh == float(‘inf’) or lh == float(‘inf’):
• ———–return False
• ——-else:
• ———–return abs(rh - lh) < 2
• —def height(self, root):
• ——-if not root:
• ———–return 0
• ——-rh = self.height(root.right)
• ——-lh = self.height(root.left)
• ——-if abs(rh - lh) > 1:
• ———–return float(‘inf’)
• ——-else:
• ———–return max(rh, lh) + 1

Question 18

symmetric tree

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

• ——–1
• —-2 2
• –3 4 4 5

Example 1:

Input: root = [1,2,2,3,4,4,3]
Output: true

Answer 18

1. think same tree, but symmetric
2. binary tree means recursion! operate on one, do the same on the next list of trees!

time: O(n), we see every node
space: O(n), logN if we have a balance tree, but we could have linked-list style tree

class Solution:

• —def isSymmetric(self, root):
• ——-if not root:
• ———–return True
• ——-return self.symmetric_helper(root.left, root.right)
• —def symmetric_helper(self, n1, n2):
• ——-if not n1 and not n2:
• ———–return True
• ——-if not n1 or not n2:
• ———–return False
• ——-if n1.val == n2.val:
• ———–if self.symmetric_helper(n1.left, n2.right) and self.symmetric_helper(n1.right, n2.left):
• —————return True
• ———–else:
• —————return False

Question 19

404. Sum of Left Leaves

Given the root of a binary tree, return the sum of all left leaves. (root is not a leaf node)

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 24
Explanation: There are two left leaves in the binary tree, with values 9 and 15 respectively.

Answer 19

Morris tree traversal is the most advanced (iterative method) but I didn’t learn it so idfk

1. follow binary search tree patterns. perform action on current node, repeat for left and right!
2. check if leaf node each time. if so return cur value if it is left, if not return 0
3. if it is NOT a leaf node, check left and right. if left or right, call the helper on both and return their sum. Set a flag in the call for left which is true if it is the left node, false if right.

time: O(n), we go through all the entire list of nodes
space: O(n), recursive space. we could do it iteratively too. with some sort of queue I think

class Solution:

• —def sumOfLeftLeaves(self, root):
• ——-if not root:
• ———–return 0
• ——-self.sum = 0
• ——-cur = root
• ——-return self.helper(cur, False)
• —def helper(self, cur, left):
• ——-if not cur:
• ———–return 0
• ——-if cur.left or cur.right:
• ———–l = r = 0
• ———–if cur.left:
• —————l = self.helper(cur.left, True)
• ———–if cur.right:
• —————r = self.helper(cur.right, False)
• ———–return l + r
• ——-else:
• ———–if left:
• —————return cur.val
• ———–else:
• —————return 0