Category: tree_bfs
-
LeetCode 653: Two Sum IV – Input is a BST
link Recursive With an inorder traversal, we can sort the values in linear time. Then, we can use two pointers approach to search for the pair, again in linear time. Time: , space: . Keeping track of already seen values, we can search the pair while we are traversing the tree. Iterative BFS + seen…
-
LeetCode 127: Word Ladder
link Unidirectional BFS The problem is to find the shortest path in an undirected word graph from beginWord to endWord. An edge means: is a word in wordList and Hamming distance between the words and is 1. We use BFS. Say and are the vertex and edge sets of the word graph. Here, . If…
-
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: .
unreasonably effective 