Category: foundational_interview
-
LeetCode 364: Nested List Weight Sum II
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:…
-
LeetCode 98: Validate Binary Search Tree
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.
-
LeetCode 236: Lowest Common Ancestor of a Binary Tree
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…
-
LeetCode 199: Binary Tree Right Side View
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…
-
LeetCode 105: Construct Binary Tree from Preorder and Inorder Traversal
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…
-
LeetCode 108: Convert Sorted Array to Binary Search Tree
link Recursive Like binary search, we recursively make mid the root and mid‘s left and right sub-lists the left and right subtrees. Time: There are levels and due to slicing, each level has copies. So, like merge-sort, total time is . Space: . Slicing is not necessary, we could pass around (lo, hi) — significantly…
-
LeetCode 124: Binary Tree Maximum Path Sum
link Recursive In the binary tree, there are two types of path: (1) linear (2) curved. Sum on a linear path may contribute to parent’s sum. Sum on a curved path does not contribute to parent’s sum. Say is the linear sum of the node — sum on a linear path that ends at .…
-
LeetCode 226: Invert Binary Tree
link Recursive We swap the children recursively, bottom-up. Time: , space: . Or, top-down: Iterative With stack, we simulate top-down swaps.
-
LeetCode 297: Serialize and Deserialize Binary Tree
link Recursive We serialize the tree in pre-order like: . During deserialization, we use a stack to parse nested parentheses or brackets. Time: , space: . With preorder as: , we can deserialize more tersely using recursion: Iterative With levelwise travesal, we can (de)serialize iteratively. We use “” as a serialization for None. During serialization,…
-
LeetCode 543: Diameter of Binary Tree
link Recursive Diameter is the edge count along the longest path. The longest path going through a node can have parts from both left and right subtrees. It is hard to define diameter going through a node in terms of diameter of its children. . However, it is easy to define in terms of height…
unreasonably effective 