Python Forum
general tree traversal
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
general tree traversal
#1
Hello all,
I'm refreshing my memory on tree traversal (just because) and I'd appreciate any comments/feedback on my preorder traversal and breadth first traversal implementations in the below code snippet please? I'd be interested to know how others might approach these traversals given the input of the Node class I've implemented.
Whilst my solution works for my Node class it would be great to get your feedback on it and any issues I may have overlooked.

Overview:
Node class, a node created with node_id on init. A node can have zero or more children
functions:
add_child(), adds a child of type Node to list (node_children), could be zero or more nodes.
preorderTraversal, takes parameter of list and returns ordered list of nodes visited.
breadthFirstTraversal, parameters, empty list and queue. Returns ordered list of nodes visited.
Both functions are invoked by the node instance as the root of traversal.

Main: I've set up nodes, invoked traversal calls and printed results. I thought it easier to do in main rather than paste unittest script.

Thanks for reading!

from queue import Queue


class Node():

    """ Node class for general tree implementation
    Instance functions:
    - add_child
    - preorderTraversal
    - breadthFirstTraversal
    """
    def __init__(self, node_id):

        """setup logging, attach logger to handlers and instatiante Node  """
        self.node_children = []
        self.node_id = node_id

    def __str__(self):

        """ return node_id"""
        return self.node_id

    def add_child(self, child):

        """Instance function to add node to parent"""
        # add child to parent
        self.node_children.append(child)

    def preorderTraversal(self, preorder_list):

        """Traverse a general tree in preorder. Entry point the invoking node.
        Each node traversed is appended to a list

        Parameters: preorder_list Type list: element Type Node()
        Return: list of nodes traversed in preorder"""
        # add node to list preorder_list
        preorder_list.append(self)
        # recursively call self for each of node node_children
        for i in self.node_children:
            i.preorderTraversal(preorder_list)

        # once all nodes have been visited return list of nodes in preorder
        return preorder_list

    def breadthFirstTraversal(self, node_queue, visited):
        """ Traverse gerneral tree breadth first order, return ordered list"""

        # self has been visited add node to list
        visited.append(self)

        # build the queue
        for i in self.node_children:
            node_queue.put(i)

        # process the queue
        while node_queue.qsize() != 0:
            return node_queue.get().breadthFirstTraversal(node_queue, visited)

        # base case empty queue
        return visited


def main():

    # create nodes
    root = Node('root')
    node1 = Node('node1')
    node2 = Node('node2')
    node3 = Node('node3')
    node4 = Node('node4')
    node5 = Node('node5')
    node6 = Node('node6')
    node7 = Node('node7')
    node8 = Node('node8')
    node9 = Node('node9')
    node10 = Node('node10')
    node11 = Node('node11')
    
    # add nodes to parent
    root.add_child(node1)
    root.add_child(node2)
    root.add_child(node3)
    node1.add_child(node4)
    node4.add_child(node5)
    node4.add_child(node6)
    node4.add_child(node7)
    node5.add_child(node11)
    node3.add_child(node8)
    node8.add_child(node9)
    node8.add_child(node10)
   
    # root
    # node1  node2   node3
    # node4              #node8
    # node5, node6, node7    node9, node10
    # node11
   
    #list for traversal results
    visited = []
    
    #queue to pass to breadth first traversal function
    gTree_queue = Queue()

    #invoke breadthFirstTraversal passing empty queue & list
    visited = node4.breadthFirstTraversal(gTree_queue, visited)
    
    print('breadthFirstTraversal')
    for i in visited:
        print(i)
    print('preorderTraversal')
    visited.clear()

    #invoke preorderTraversal passing empty list
    visited = node4.preorderTraversal(visited)
    for i in visited:
        print(i)

if __name__ == '__main__':

    main()
Reply
#2
That's a really odd way to do it. Step through your breadth first example:

Node 4, add Nodes 5-7, call node 5
Node 5, add Node 11, call node 6
Node 6, add nothing, call node 7
Node 7, add nothing, call node 11

So you have nodes calling nodes that are not their descendants. This is also basically recursive, with a recursion depth equal to the size of the tree. For a large tree, you could run into the recursion limit. It wouldn't even have to be that large.

I would normally do a breadth first as a loop in the node that calls it. Something like:

visited = []
node_queue.put(self)
while node_queue.qsize() != 0:
    next_node = node_queue.get()
    visited.append(next_node)
    for child in next_node.node_children:
        node_queue.put(child)
Craig "Ichabod" O'Brien - xenomind.com
I wish you happiness.
Recommended Tutorials: BBCode, functions, classes, text adventures
Reply
#3
Thank you for your input, great to hear your views and great suggestion, nice and simple!
Explanation of my logic (yes, incorrect and lazy logic with an over reliance on recursion for trivial tasks), build the queue and then visit.

Thanks again, great response!!
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  A generic breadth first traversal function Gribouillis 2 2,982 Jul-12-2019, 12:26 AM
Last Post: rootVIII

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020