def get_paths(index, stack):                                        # O(logN)
    """
    >>> get_paths(10, [])
    ['left', 'right', 'left']
    """
    if index == 1:                                                  # O(1)
        return stack                                                # O(1)

    is_odd = index % 2                                              # O(1)
    if not is_odd:                                                  # O(1)
        parent_node = index / 2                                     # O(1)
        stack.append('left')                                        # O(1)
        return get_paths(parent_node, stack)                        # O(1)

    parent_node = (index - 1) / 2                                   # O(1)
    stack.append('right')                                           # O(1)
    return get_paths(parent_node, stack)                            # O(logN)