Convert Binary Tree to Graph

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.

Conversion

We define a binary tree node like this:

1
2
3
4
5
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None

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.

1
2
3
4
5
6
7
8
graph = collections.defaultdict(list)
def convert(node, parent = None):
if node:
graph[node].append(parent)
graph[parent].append(node)
convert(node.left, node)
convert(node.right, node)
convert(root)

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.

1
2
3
4
5
6
7
8
9
queue = collections.deque(root)
seen = set(queue)
while queue:
node = queue.popleft()
if node:
for n in graph[node]:
if n not in seen:
seen.add(n)
queue.append(n)
0%