Category: tree_dfs
-
LeetCode 1110: Delete Nodes And Return Forest
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…
-
LeetCode 230: Kth Smallest Element in a BST
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 ->…
-
LeetCode 104: Maximum Depth of Binary Tree
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: .
-
LeetCode 2458: Height of Binary Tree After Subtree Removal Queries
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 ,…
-
LeetCode 285: Inorder Successor in BST
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…
-
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…
unreasonably effective 