unreasonably effective

link Recursive Deleting a node affects at most three other nodes: (1) parent (2) left child (3) right child. After delete, the children become roots of new trees while parent looses one child. So, with a single DFS, for each node, we can update these three pointers while collecting new roots. The updates must be…

link Recursive The value of the k-th visited node inorder is our answer. Time: , space: . Follow-up: If we do the kth smallest query often, we could keep track of the size (or count of nodes) for each subtree. Then, to find the k-th smallest, we would need to just traverse the root ->…

link Recursive Time: , space: . Iterative Simulate the bottom up recursion with stack, visited set, and node height dict. Time: , space: . Use threaded binary tree or Morris traversal. Time: , space: .

link Recursive We can simulate deleting of the subtree by considering root.val == q as if it were root.val == None. Time: , space: . Deleting a rooted subtree may or may not affect the longest simple path. From the level-wise view of the tree we make the below observations: Given a to-be-deleted node ,…

link Recursive If we traverse the tree inorder, then the inorder successor of will be visited right after . So, during inorder traversal, we return the first node after the event . Time: , space: . The above approach works for any binary tree. Since we have a BST, we can do better. If has…

link Two pass Forest Recursive Each NestedInteger can be thought of as a tree. So, the problem involves a forest of trees. We first find the maximum height of these trees which is the max depth for the forest. Then, we sum up the weighted sum of all trees in the forest. Time: , space:…

link Recursive For BST . So, for the left subtree, is an upper bound. Similarly, for the right subtree, is a lower bound. We recursively validate the invariant: . Time: , space: . Iterative With an explicit stack, we simulate the top-down recursion.

link Recursive Between the two paths: (1) p -> root and (2) q -> root, the LCA -> root subpath is common. So, if the two paths have different lengths, the difference is in the prefix up to LCA. We can use two pointers to traverse the two paths such that they reach LCA at…

link Recursive We do DFS preferring right. With root , the left subtree contributes to the right-side view only if, it is deeper than the right subtree. In that case, prefix of view is from right subtree and suffix of view is from left subtree. We pass around depth to decide if left subtree should…

link Recursive We want to formulate the problem recursively: From preorder we know val of root. Since values are distinct, we can find the inorder position of the root’s val and that gives us lengths of left and right subtrees. From the subtree lengths and root’s position, now we know the (start, end) indices of…