SWE Interview preparation

https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/ Given two binary trees  original  and  cloned  and given a reference to a node  target  in the original tree. The  cloned  tree is a  copy of  the  original  tree. Return  a reference to the same node  in the  cloned  tree. Note  that you are  not allowed  to change any of the two trees or the  target  node and the answer  must be  a reference to a node in the  cloned  tree. Follow up:  Solve the problem if repeated values on the tree are allowed.   Example 1: Input: tree = [7,4,3,null,null,6,19], target = 3 Output: 3 Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree. Example 2: Input: tree = [7], target = 7 Output: 7 Example 3...

https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/ Given the  root  of a binary tree, the level of its root is  1 , the level of its children is  2 , and so on. Return the  smallest  level  X  such that the sum of all the values of nodes at level  X  is  maximal .   Example 1: Input: [1,7,0,7,-8,null,null] Output: 2 Explanation: Level 1 sum = 1. Level 2 sum = 7 + 0 = 7. Level 3 sum = 7 + -8 = -1. So we return the level with the maximum sum which is level 2.   Note: The number of nodes in the given tree is between  1  and  10^4 . -10^5 <= node.val <= 10^5

https://leetcode.com/problems/nested-list-weight-sum-ii/ https://www.lintcode.com/problem/nested-list-weight-sum-ii/description Given a nested list of integers, return the sum of all integers in the list weighted by their depth. Each element is either an integer, or a list -- whose elements may also be integers or other lists. Different from the  previous question  where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight. Example 1: Input: [[1,1],2,[1,1]] Output: 8 Explanation: F our 1's at depth 1, one 2 at depth 2. Example 2: Input: [1,[4,[6]]] Output: 17 Explanation: O ne 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 1*3 + 4*2 + 6*1 = 17. --- Related problems 339-nested-list-weight-sum 341-flatten-nested-list-iterator ---

https://leetcode.com/problems/binary-tree-vertical-order-traversal/ https://www.lintcode.com/problem/binary-tree-vertical-order-traversal/description Given a binary tree, return the  vertical order  traversal of its nodes' values. (ie, from top to bottom, column by column). If two nodes are in the same row and column, the order should be from  left to right . Examples 1: Input: [3,9,20,null,null,15,7] 3 /\ / \ 9 20 /\ / \ 15 7 Output: [ [9], [3,15], [20], [7] ] Examples 2: Input: [3,9,8,4,0,1,7] 3 /\ / \ 9 8 /\ /\ / \/ \ 4 01 7 Output: [ [4], [9], [3,0,1], [8], [7] ] Examples 3: Input: [3,9,8,4,0,1,7,null,null,null,2,5] (0's right child is 2 and 1's left child is 5) 3 /\ / \ 9 8 /\ /\ / \/ \ 4 01 7 /\ / \ 5 2 Output: [ [4], [9,5], [3,0,1], [8,2], [7] ] --- Intuition Order L to R must be preserved for each level = > L...

https://leetcode.com/problems/symmetric-tree/ Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree  [1,2,2,3,4,4,3]  is symmetric: 1 / \ 2 2 / \ / \ 3 4 4 3 But the following  [1,2,2,null,3,null,3]  is not: 1 / \ 2 2 \ \ 3 3 Follow up:  Solve it both recursively and iteratively --- Iterative - level order - queue based Offer 2 nodes, and remove 2 nodes at a time Offer nulls as well, don't filter them out Offer mirror nodes together n1.left, n2.right n1.right, n2.left -- Time - O(n) Space - O(n) ---

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/ You are given a  perfect binary tree  where all leaves are on the same level, and every parent has two children. The binary tree has the following definition: struct Node { int val; Node *left; Node *right; Node *next; } Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to  NULL . Initially, all next pointers are set to  NULL . Follow up: You may only use constant extra space. Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem. Example 1: Input: root = [1,2,3,4,5,6,7] Output: [1,#,2,3,#,4,5,6,7,#] Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next p...

https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/ Given a binary tree struct Node { int val; Node *left; Node *right; Node *next; } Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to  NULL . Initially, all next pointers are set to  NULL . Follow up: You may only use constant extra space. Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem. Example 1: Input: root = [1,2,3,4,5,null,7] Output: [1,#,2,3,#,4,5,7,#] Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level. Constraints: The number of nodes in the given tree is less than  6000 . -100 <= node.v...

https://leetcode.com/problems/maximum-width-of-binary-tree/ Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a  full binary tree , but some nodes are null. The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the  null  nodes between the end-nodes are also counted into the length calculation. Example 1: Input: 1 / \ 3 2 / \ \ 5 3 9 Output: 4 Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9). Example 2: Input: 1 / 3 / \ 5 3 Output: 2 Explanation: The maximum width existing in the third level with the length 2 (5,3). Example 3: Input: 1 / \ 3 2 ...

https://leetcode.com/problems/find-largest-value-in-each-tree-row/ You need to find the largest value in each row of a binary tree. Example: Input: 1 / \ 3 2 / \ \ 5 3 9 Output: [1, 3, 9] --- Time - O(n) Space - O(2 ^ h) - # nodes at last level ---

https://leetcode.com/problems/average-of-levels-in-binary-tree/ Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array. Example 1: Input: 3 / \ 9 20 / \ 15 7 Output: [3, 14.5, 11] Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11]. Note: The range of node's value is in the range of 32-bit signed integer. --- Note - use long for sum to prevent Integer overflow

Given a N-ary tree, check whether it is symmetric around its root. N-ary tree is symmetric if value and shape look the same when reflected at the root. Note  -  Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value  Example1 Input: root = [5,null,3,5,3,null,10,null, 15, null, 10]   Output: true Example2 Input: root = [5,null,3,5,3,null,10,25, null, 15, null, 10]   Output: false Example3 Input: root = [5,null,3,5,3,null,10, null, 15, null, 25, 10] Output: false Example4 Input: root = [5,null,3,5,3,null,10,25, null, 15, null, 35, 10] Output: false --- Intuition Check each level, and check if its symmetric Symmetric => Node val, and number of children at each end of level order should be the same

https://leetcode.com/problems/find-bottom-left-tree-value/ Given a binary tree, find the leftmost value in the last row of the tree. Example 1: Input: 2 / \ 1 3 Output: 1 Example 2: Input: 1 / \ 2 3 / / \ 4 5 6 / 7 Output: 7 Note:  You may assume the tree (i.e., the given root node) is not  NULL --- Intuition For getting last level, we need level by level traversal => BFS - Queue based. Track the first element at each level, after the last level, we have answer -- Time - O(n) Space - O(n) ---