Imagine a data structure whereby you have a graph full of nodes.
Each node has data, a single parent and 0+ children.
class Node:
def __init__(self, data) -> None:
self.data = data
self.parent = None
self.children = []
The graph handles connecting the nodes as such
class Graph:
def __init__(self, node) -> None:
self.root_node = node
def add_relationship(self, parent, child):
if not parent.parent:
parent.parent = self.root_node
self.root_node.children.append(parent)
parent.children.append(child)
child.parent = parent
For constraints, lets say that there will be anywhere from 2 to 100 nodes total.
Now, let’s suppose I want to add a method to the graph class that returns all the nodes in the graph that do not have children.
My first thought is recursion.
def _end_nodes(self, current_node, nodes_with_children=[], nodes_without_children=[]):
for node in current_node.children:
if node.children:
nodes_with_children.append(node)
else:
nodes_without_children.append(node)
if not nodes_with_children:
return []
return [nodes_without_children] + self._end_nodes(nodes_with_children.pop(0))
But this yields the desired answer repeated however many times the recursive function is called.
Of course, I could just get a single element from the returned array
def __repr__(self) -> str:
return str(self._end_nodes(self.root_node)[0])
But I feel like this is sloppy. How can I go about getting the desired results in a more succinct manner?
>Solution :
To find the nodes that lack children in a single parent, multiple children graph, you can add a method to the Graph class that traverses the entire graph and collects nodes without children.
The method is defined as below. Its basically using the BFS.
def find_nodes_without_children(self):
nodes_without_children = []
queue = [self.root_node]
while queue:
current_node = queue.pop(0)
if not current_node.children:
nodes_without_children.append(current_node)
else:
queue.extend(current_node.children)
return nodes_without_children
and you can verify it from the line of code below
print([node.data for node in graph.find_nodes_without_children()])
Overall Implementation will looks something like below
class Node:
def __init__(self, data) -> None:
self.data = data
self.parent = None
self.children = []
class Graph:
def __init__(self, node) -> None:
self.root_node = node
def add_relationship(self, parent, child):
if not parent.parent:
parent.parent = self.root_node
self.root_node.children.append(parent)
parent.children.append(child)
child.parent = parent
def find_nodes_without_children(self):
nodes_without_children = []
queue = [self.root_node]
while queue:
current_node = queue.pop(0)
if not current_node.children:
nodes_without_children.append(current_node)
else:
queue.extend(current_node.children)
return nodes_without_children
FYI: The both Time and Space complexity is O(N)