trees, LL,

Question 1

iterative in order traversal

Answer 1

–

Question 2

binary tree in order traversal

don’t code

Answer 2

review

Question 3

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

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

don’t code

Answer 3

review

Question 4

https://leetcode.com/problems/diameter-of-binary-tree/description/

code!!

Answer 4

helper func returns [height, diam].

height = 1 + max(left height, right height)

diam = max ( max(left diam, right diam), left height + right height )

Question 5

https://leetcode.com/problems/balanced-binary-tree/description/

don’t code

Answer 5

review

Question 6

https://leetcode.com/problems/subtree-of-another-tree/description/

given root and subroot, det whether the tree w/ head subroot is contained within the tree w/ head root

don’t code but must review logic

Answer 6

use isSameTree() helper func. call it whenever root.val == subRoot.val. if !isSameTree, DON’T return false immediately; keep going down the tree

Question 7

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/

don’t code but must review logic

Answer 7

head of the tree is the middle element in the array. head.left = middle element of left half. head.left = middle element of right half.

Question 8

https://leetcode.com/problems/path-sum/description/

code

Answer 8

must do the node.left == null && node.right == null check; if the only check is done for node == null, cases will be missed

Question 9

https://leetcode.com/problems/construct-string-from-binary-tree/

code

Answer 9

use string.join(“”, list.subList()) to get rid of outer ( ).
only add ( ) for a null child in the case of a null left child and non-null right child

Question 10

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/

of binary SEARCH tree, not binary tree

don’t code but must review logic

Answer 10

if we encounter a node whose val is == to the vals of either of the input nodes, immediately return.

lca can also be a node whose value is btwn the two nodes. traverse bst by comparing the node’s val to greater and lesser

Question 11

https://leetcode.com/problems/insert-into-a-binary-search-tree/description/

don’t code but must review logic

Answer 11

no need for fancy insertions; just insert where there is a null node.

if (val < node.val and node.left == null), insert node there and break.

traverse bst based on property.

Question 12

https://leetcode.com/problems/delete-node-in-a-bst/description/

code and review logic!!

Answer 12

if (val > curr.val), curr.right = recurse(curr.right, val).

same for <.

if ==, first handle cases where curr has a null child.
if it doesn’t, we replace curr.val with the val of the rightmost node in curr’s left subtree (or the leftmost node in the right subtree - either works).
then, make a recursive call on whichever subtree you took the value from

Question 13

https://leetcode.com/problems/count-good-nodes-in-binary-tree/

don’t code but must review logic

Answer 13

helper function takes in node, info, and greatestVal.

if node.val >= greatestVal, update info.

update greatestVal accordingly.

Question 14

https://leetcode.com/problems/validate-binary-search-tree/description/

don’t code but must review logic

Answer 14

create a helper function. must pass in min valid value and max valid value into it

Question 15

https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/

code!!

Answer 15

.

Question 16

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

code and review logic

Answer 16

remember these two key observations:
- the first element in the preorder array is always the root
- find the value of the root in the inorder array. everything to the left of that value is in the root’s left subtree; everything to the right is in the root’s right subtree.

splitIdx also reveals where the split occurs in the preorder array - [1, mid] in preorder is left subtree

use Arrays.copyOfRange to get subarrays

Question 17

https://leetcode.com/problems/unique-binary-search-trees/

code helper func only, and review logic

Answer 17

use caching.
num trees i can make w/ 3 nodes =
(remember 1 root node!)
(num trees with 0 nodes in left subtree * num trees with 2 in right)
+
(1 node in left * 1 node in right)
+ …

2 base cases: (0, 1) and (1, 1)

Question 18

https://leetcode.com/problems/sum-root-to-leaf-numbers/description/

don’t code but must review logic

Answer 18

use global var sum.
pass an int ‘path’ into the helper function. path = 10 * path + node.val.

Question 19

https://leetcode.com/problems/house-robber-iii/description/

code and review logic

Answer 19

instead of tracking the sum from top to bottom, consider it from bottom to top

helper function returns [nodeInc, nodeExc].
no need to keep track of sum variable; just return max of the result [ ] in the main function

nodeExc = max(both left) + max(both right)

nodeIncluded = node.val + left[1] + right[1];

Question 20

https://leetcode.com/problems/flip-equivalent-binary-trees/description/

don’t code; review logic of return stmt only

Answer 20

.

Question 21

https://leetcode.com/problems/all-possible-full-binary-trees/description/

code and review logic

Answer 21

• full binary trees can’t have even num of nodes.
• BC n = 1. the tree just has 1 node.
• num nodes in left subtree is in the range [1, n - 2]

Question 22

https://leetcode.com/problems/trim-a-binary-search-tree/description/

code and review logic

Answer 22

it’s a BST so if a node has a value too large, all of its right subtree must be cut, and if a node has a value too small, all of its left subtree must be cut.

when you encounter a node that must be cut, you must traverse the tree until you reach a valid node

Question 23

https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/description/

don’t code but must review logic

Answer 23

must use gloval var for sum

review code

Question 24

https://leetcode.com/problems/binary-search-tree-iterator/description/

code and review logic

Answer 24

when adding to stack in the constructor, always go left, starting from root. we never add all of the nodes to the stack; only O(h) space

in the next() func, pop a node off the stack, get its right child, and then go left adding to stack

Question 25

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/ code and review logic

Answer 25

PRE order traversal use global var for index. split serialized string at commas.

Question 26

https://leetcode.com/problems/binary-tree-maximum-path-sum/ code and review logic

Answer 26

get L and R from recursive calls. maxBranch = max ( max(L, R) + node.val , node.val). this is also the return value maxOverall = (L + R + node.val, maxBranch) update global var sum as needed.

Question 27

reverse LL iterative and recursive code

Answer 27

.

Question 28

https://leetcode.com/problems/palindrome-linked-list/description/ don't code; review logic

Answer 28

at the beginning, must include if (head == null || head.next == null) return true;

Question 29

https://leetcode.com/problems/remove-linked-list-elements/description/ don't code; review logic

Answer 29

use dummy head. if node.val != val, curr.next = node and move both ptrs forward. MUST REMEMBER curr.next = null after while loop exits. otherwise, elements at the end won't be removed

Question 30

https://leetcode.com/problems/intersection-of-two-linked-lists/description/ code again

Answer 30

.

Question 31

https://leetcode.com/problems/reorder-list/description/ don't code; review logic

Answer 31

1. reverse list starting from mid. then it becomes clear how to merge 2. review order of reassigning and advancing pointers 3. handle case of odd length list

Question 32

https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/ don't code; review logic

Answer 32

advance fast ptr n times (while fast is not null and n-- > 0). use dummy head to avoid handling edge cases.

Question 33

https://leetcode.com/problems/check-completeness-of-a-binary-tree/description/

Answer 33

the idea is that once you encounter a null node, all nodes after it in the queue must also be null have a boolean nullEncountered outside the main loop

Question 34

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

Answer 34

bfs. add to queue(Item(node, idx)) idx of a node's left child = idx * 2 idx of a node's right child = idx * 2 + 1

Question 35

https://leetcode.com/problems/convert-bst-to-greater-tree/description/

Answer 35

sum must be in Info class

Question 36

https://leetcode.com/problems/find-duplicate-subtrees/description/

Answer 36

serialization = cur.val + "," + postorder(cur.left, map, res) + "," + postorder(cur.right, map, res); return this serialization in the helper function

Question 37

https://leetcode.com/problems/minimum-distance-between-bst-nodes/description/ review logic

Answer 37

traverse the tree in this way: left add to list right now you have a list of all tree values in sorted order. get min difference

Question 38

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

Answer 38

bfs. to insert right to left: level.add(0, node.val);