• + 0 comments

    Python recursion solution explained.

    def getNode(llist, positionFromTail):
            
        def traverse(head, n=0):
            # Stop recursion condition. Stop when there is no children (reached tail)
            if head.next is None:
                return (n, head.data)
            
            # Save max_depth and possible answer value
            max_depth, ans = traverse(head.next, n+1)
            # We will exit this part only when we reach max depth of the list
            
            # As we are traversing backwards (getting outside of the recursion)
            # we check our main condition for the position from the tail
            if max_depth-positionFromTail == n:
                # If we meet the condition we return the value
                return (max_depth, head.data)
            else:
                # If the condition is not met yet or has already been met
                # we return the possible answer and the depth
                return (max_depth, ans)
        
        # Return the answer
        return traverse(llist)[1]