Leetcode: Trees Flashcards
strategies for trees
- linear searching doesn’t work since the array representing a tree isn’t linear
- recursion is great to solve these because each node is itself a subtree, so it will be evaluated the same way
- remember to always have a good base case
- call the left tree, right tree, and merge the results!
https://www.youtube.com/watch?v=s2Yyk3qdy3o&t=140s
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.
- search through with any of the traversals, postorder, inorder, preorder, preorder is easiest in my experience
- 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
- 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
invert a binary tree
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
calculate height of a binary tree, height of an n-ary tree
- start with if node is null, which will give 0
- then if node only has a root, that gives 1
- 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)
- 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
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.
- break it down into smaller problems, think tree based problems
- 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
- if there are 2 options on the left, 2 on the right, then we have 4 total combinations
- 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)
- 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.
- add values to the map as soon as you get the final sum for that n.
- 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
- same idea as above, except instead of memoizing we us a dp array
- 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]
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]]
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
- given the root i, the left roots are equal to i-1, and the right are equal to n-i
- 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
- 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
- base case is if start > end, return [None], when start==end that is okay (think n=1, (1,1))
- next what do we put in each method signature, how do we calculate it for left /right?
- (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)
- 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
- 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
validate a binary search tree
- get a base case, apply conditions to both nodes, repeat on each node
- the starter code is not enough, we need to keep track of the lowest/highest values we can be between
- create a helper method with default low/high, check root value is less/greater than them, recursively call the helper on each node.
- 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
postorder traversal
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=””)
- 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
inorder traversal
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
preorder traversal
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)
binary tree level order traversal, return each level as a list
return list[list[int]]
- 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
- find depth, create the output accordingly, then append to the output based on the level
- BONUS don’t need to know depth
- each time you call helper, check the length of output vs level, if they are equal add another level to it
- 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
- 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))
right view of binary tree
print the right view of the binary tree
- level order
- recursive level order, understand len(output)==level is the primary way to handle the recursion
- 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!
- 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)
- 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
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:
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
- realize you NEVER need to compare to previous value, in a BST, the num on the right is ALWAYS LARGER
- 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
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.
- binary tree, perform action on root node, copy for left and right.
- 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!)
- 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
level order of an n-ary tree
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
- recursive BFS means that you need to keep track of the level
- if you are at a new level and it has not been added to the response, check, and add it
- 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
