Category: foundational_interview
-
LeetCode 101: Symmetric Tree
link Iterative For the tree to be symmetric, each level (including missing children) must be a palindrome. With a single BFS we process an entire level per iteration and check if the level is a palindrome. Time: , space: . Recursive For a subtree rooted at a node, although we cannot define symmetry in terms…
-
LeetCode 987: Vertical Order Traversal of a Binary Tree
link Recursive Each node has three coordinates: row, col, val. The problem is to sort the node-values by its coordinates: column id, row id and value. We emit column values in sorted order: start with lowest column id and go towards highest. Tracking column id is easy: if has col, its left child has (col-1)…
-
LeetCode 116: Populating Next Right Pointers in Each Node
link In each iteration of BFS we can process the entire level, linking the nodes with next pointer. Time: , space: . Follow-up: Use only constant extra space. Since the implicit stack of recursion is not counted as extra space, we can connect siblings. The right child should point to the left cousin.
-
LeetCode 103: Binary Tree Zigzag Level Order Traversal
link In each iteration of BFS, we process entire level. For odd levels, order is reversed. Time: , space: .
-
LeetCode 102: Binary Tree Level Order Traversal
link In each iteration of BFS, we process the entire level. Time: , space: .
-
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…
unreasonably effective 