Add methods to traverse leaves - ie. next_leaf(), previous_leaf()

Issue #32 resolved
phoebebright
created an issue

Can supply the code I wrote but I'm sure others can do better or maybe there is a way of doing this with just existing calls! Useful to be able to traverse just the leaf nodes and to be able to return all_leaves() as a list.

Comments (2)

  1. Anonymous

    This is the code I'm using to traverse leaves:

    def go_down(next):
       """
       travel down a left hand side of a tree to find the next leaf
       """
        while next and not next.is_leaf():
            next = next.get_first_child()
            
        return next
    
    def go_down_reverse(next):
        """
        travel down the right hand side of a tree to find the previous leaf
        used when traversing backwards
        """
        while next and not next.is_leaf():
            next = next.get_last_child()
            
        return next
        
    def go_along(next):
        """
        move right and then down to get next leaf along
        """
        if next and next != next.get_last_sibling():
            return go_down(next.get_next_sibling())
            
        else:
            return  go_up(next)
    
    def go_back(next):
        """
        move left and then down to get previous leaf
        used when traversing in reverse
        """
        
        if next and next != next.get_first_sibling():
            return go_down_reverse(next.get_prev_sibling())
            
        else:
            return  go_up_reverse(next)
     
    def go_up(next):
        """
        move back up until there is another opportunity to go along and find the next leaf
        """
        while next and next == next.get_last_sibling():
            next = next.get_parent()
    
        if next:    
            return go_along(next)
        else:
            #end of the line
            return None
    
    def go_up_reverse(next):
        """
        move back up until there is an opportunity to go back and find the next leaf
        used when traversing in reverse
        """
        
        while next and next == next.get_first_sibling():
            next = next.get_parent()
    
        if next:    
            return go_back(next)
        else:
            #end of the line
            return None
            
    def next_leaf(next):
        """
        traverse tree to find the next leaf moving left to right
        """
        if not next.is_leaf():
            return go_down(next)
            
        else:
            return go_along(next)
    
    def previous_leaf(next):
        """
        traverse tree to find previous leaf moving right to left
        """
        if not next.is_leaf():
            return go_down_reverse(next)
            
        else:
            return go_back(next)
        
     
    def first_leaf(next):
        return go_down(next)
    
  2. Log in to comment