SWE Interview preparation

https://github.com/openset/leetcode/tree/master/problems/find-leaves-of-binary-tree https://leetcode.com/problems/find-leaves-of-binary-tree/ https://www.lintcode.com/problem/find-leaves-of-binary-tree/description Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.   Example: Input: [1,2,3,4,5]     1 / \ 2 3 / \ 4 5 Output: [[4,5,3],[2],[1]]   Explanation: 1. Removing the leaves  [4,5,3]  would result in this tree: 1 / 2   2. Now removing the leaf  [2]  would result in this tree: 1   3. Now removing the leaf  [1]  would result in the empty tree: [] ----- Intuition Need info from both left, and right child to determine if current node is leaf node Post Order DFS Consider looking up the tree from below where the level is...

https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/ https://github.com/openset/leetcode/tree/master/problems/binary-tree-longest-consecutive-sequence https://www.lintcode.com/problem/binary-tree-longest-consecutive-sequence/description Given a binary tree, find the length of the longest consecutive sequence path. The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse). Example 1: Input: 1 \ 3 / \ 2 4 \ 5 Output: 3 Explanation: Longest consecutive sequence path is 3-4-5 , so return 3 . Example 2: Input: 2 \ 3 / 2 / 1 Output: 2 Explanation: Longest consecutive sequence path is 2-3 , not 3-2-1 , so return 2 . --- Related problems 549-binary-tree-longest-consecutive-sequence-ii ---

https://leetcode.com/problems/k-diff-pairs-in-an-array/ Given an array of integers and an integer  k , you need to find the number of  unique  k-diff pairs in the array. Here a  k-diff  pair is defined as an integer pair (i, j), where  i  and  j  are both numbers in the array and their  absolute difference  is  k . Example 1: Input: [3, 1, 4, 1, 5], k = 2 Output: 2 Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5). Although we have two 1s in the input, we should only return the number of unique pairs. Example 2: Input: [1, 2, 3, 4, 5], k = 1 Output: 4 Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5). Example 3: Input: [1, 3, 1, 5, 4], k = 0 Output: 1 Explanation: There is one 0-diff pair in the array, (1, 1). Note: The pairs (i, j) and (j, i) count as the same pair. The length of the array won't exceed 10,000. All the integers in the given input belong to the ra...

https://leetcode.com/problems/maximum-binary-tree/ Given an integer array with no duplicates. A maximum tree building on this array is defined as follow: The root is the maximum number in the array. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number. The right subtree is the maximum tree constructed from right part subarray divided by the maximum number. Construct the maximum tree by the given array and output the root node of this tree. Example 1: Input: [3,2,1,6,0,5] Output: return the tree root node representing the following tree: 6 / \ 3 5 \ / 2 0 \ 1 Note: The size of the given array will be in the range [1,1000]. --- Recursion Time - O(N ^ 2) - worst case - sorted array, max elem is at end, O(N log N) - average case - balanced tree Space - O(N) - recursion stack - worst case, sorted array, N levels, O( log N) - average case ---

https://leetcode.com/problems/convert-bst-to-greater-tree/ Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST. Example: Input: The root of a Binary Search Tree like this: 5 / \ 2 13 Output: The root of a Greater Tree like this: 18 / \ 20 13 Note:  This question is the same as 1038:  https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/ --- Related problems 1038-binary-search-tree-to-greater-sum --- Time - O(N) Space - O(N) --

https://leetcode.com/problems/boundary-of-binary-tree https://github.com/openset/leetcode/tree/master/problems/boundary-of-binary-tree https://www.lintcode.com/problem/boundary-of-binary-tree/description Given a binary tree, return the values of its boundary in  anti-clockwise  direction starting from root. Boundary includes left boundary, leaves, and right boundary in order without duplicate  nodes .  (The values of the nodes may still be duplicates.) Left boundary  is defined as the path from root to the  left-most  node.  Right boundary  is defined as the path from root to the  right-most  node. If the root doesn't have left subtree or right subtree, then the root itself is left boundary or right boundary. Note this definition only applies to the input binary tree, and not applies to any subtrees. The  left-most  node is defined as a  leaf  node you could reach when you always firstly travel to the left subtre...

https://leetcode.com/problems/inorder-successor-in-bst/ https://github.com/openset/leetcode/tree/master/problems/inorder-successor-in-bst https://www.lintcode.com/problem/inorder-successor-in-bst/description Given a binary search tree and a node in it, find the in-order successor of that node in the BST. The successor of a node  p  is the node with the smallest key greater than  p.val .   Example 1: Input: root = [2,1,3] , p = 1 Output: 2 Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type. Example 2: Input: root = [5,3,6,2,4,null,null,1] , p = 6 Output: null Explanation: There is no in-order successor of the current node, so the answer is null .   Note: If the given node has no in-order successor in the tree, return  null . It's guaranteed that the values of the tree are unique. --- Related problems 701-insert-into-binary-search-tree ---

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/delete-nodes-and-return-forest/ Given the  root  of a binary tree, each node in the tree has a distinct value. After deleting all nodes with a value in  to_delete , we are left with a forest (a disjoint union of trees). Return the roots of the trees in the remaining forest.  You may return the result in any order.   Example 1: Input: root = [1,2,3,4,5,6,7], to_delete = [3,5] Output: [[1,2,null,4],[6],[7]]   Constraints: The number of nodes in the given tree is at most  1000 . Each node has a distinct value between  1  and  1000 . to_delete.length <= 1000 to_delete  contains distinct values between  1  and  1000 . ---

https://leetcode.com/problems/serialize-and-deserialize-n-ary-tree/ https://github.com/openset/leetcode/tree/master/problems/serialize-and-deserialize-n-ary-tree https://www.lintcode.com/problem/serialize-and-deserialize-n-ary-tree/description Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize an N-ary tree. An N-ary tree is a rooted tree in which each node has no more than N children. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that an N-ary tree can be serialized to a string and this string can be deserialized to the original tree structure. For example, you may serialize the following  3-ary  tree     as  [1 [3[5 6] 2 4]] . You do n...

https://leetcode.com/problems/merge-two-binary-trees/ Given two binary trees and 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 them 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 new tree. Example 1: Input: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 Output: Merged tree: 3 / \ 4 5 / \ \ 5 4 7   Note:  The merging process must start from the root nodes of both trees. ---

https://leetcode.com/problems/closest-binary-search-tree-value-ii/ https://github.com/openset/leetcode/tree/master/problems/closest-binary-search-tree-value-ii https://www.lintcode.com/problem/closest-binary-search-tree-value-ii/description Given a non-empty binary search tree and a target value, find  k  values in the BST that are closest to the target. Note: Given target value is a floating point. You may assume  k  is always valid, that is:  k  ≤ total nodes. You are guaranteed to have only one unique set of  k  values in the BST that are closest to the target. Example: Input: root = [4,2,5,1,3], target = 3.714286, and k = 2 4 / \ 2 5 / \ 1 3 Output: [4,3] Follow up: Assume that the BST is balanced, could you solve it in less than  O ( n ) runtime (where  n  = total nodes)? --- Related problems 270-closest-binary-search-tree-value --- ---

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ Given preorder and inorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. For example, given preorder = [3,9,20,15,7] inorder = [9,3,15,20,7] Return the following binary tree: 3 / \ 9 20 / \ 15 7 --- Related problems 106-construct-binary-tree-from-inorder ---

https://leetcode.com/problems/binary-tree-preorder-traversal/ Given a binary tree, return the  preorder  traversal of its nodes' values. Example: Input:   [1,null,2,3] 1 \ 2 / 3 Output:   [1,2,3] Follow up:  Recursive solution is trivial, could you do it iteratively? --- Intuition Recursion is trivial dfs     node.val     dfs(node.left)     dfs(node.right) Think of recursive stack trace Once function is entered, first value is printed, then 2 dfs calls are made to left, and right Do the same with explicit stack stack.push(root) while (!stack.isEmpty()) {     Node node =  stack.pop     print node.val     // push right first, so that left is on top, and root, left, right -- preorder is followed     if (node.right != null)          stack.push(node.right)     if (node.left != null)           stack.push(node...