algorithm to find nodes that lack children in single parent, multiple children graph

Question

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?

Answer 1

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)