I have been doing problems on LeetCode recently, and keep getting stuck on some graph or tree problems. I understand the underlying concepts of Graphs, Trees, and different methods of traversal just fine. For example, I can code a tree from scratch by creating a class for the Node and then passing the root to a function that traverses the tree using these interconnected node objects.
class TreeNode(): def __init__(self,val=None,left=None,right=None): self.val = val self.left = left self.right = right def BFS_tree(root): queue = [root] while queue: node = queue print(node.val) queue = queue[1:] left = node.left right = node.right if left: queue.append(node.left) if right: queue.append(node.right)
What I have trouble with is applying this when the input data structure is not already an object specially created for representing part of a Graph or a Tree.
For example, I see problems where you are supposed to use a DFS on a 2D array, with each second-level element vertex and the edges connected by i+1 and i-1 (Example)
Or array of numbers representing a combo lock where each combo 0000-9999 is a possible element on a graph (Example)
Or an array representing the BFS traversal of a tree that then must be used to delete certain elements and keep track of the disjointed trees that result (Example)
At a very high level, this makes perfect sense.
But I don't really understand how to actually code it. What are some generalized approaches I can use when thinking of a different data structure in terms of a Graph or Tree. Obviously the approach of init a Node Object, populating the graph with a Node representation of every element, and then traversing it would work... but is far too much work, especially since I want to solve these problems quickly such as in a interview!