Any binary tree can convert to a graph, because a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any acyclic connected graph is a tree.
So the only problem is how to convert the binary tree data structure to the graph data structure. Let’s figure out it.
We define a binary tree node like this:
Each tree node has two children, left and right. And for leaf node, all its children are None.
In the node traversal, we can save all node connected with this node, except None. So a leaf node has no child, in other word, this node is only connected with its parent.
graph = collections.defaultdict(list)
It’s noteworthy that the root node has a fake parent node None. So that if
len(graph[node]) == 1, the node must be leaf node.
queue = collections.deque(root)