def extract_tree(root, ordered_RD):
    """
    Extract all nodes from the tree below root node using deepth-first search.

    reture:
        a list has the structure [[node_id, start_idx, end_idx, average_RD, level_id, parent_id],\
                                  [...]...]
    """
    level = 0
    node_id = 0
    parent_id = [-1]
    to_be_processed = [root]
    next_level = []
    next_level_parent_id = []
    tree = []
    while len(to_be_processed) > 0:
        current_node = to_be_processed.pop()
        next_level.extend(current_node.children)

        # keep track of parent for updating parent id
        current_parent_id = parent_id.pop()
        next_level_parent_id.extend([node_id]*len(current_node.children))

        start, end = current_node.index_range
        ave_RD = current_node.average_RD(ordered_RD)
        tree.append([node_id, start, end, ave_RD, level, current_parent_id])
        node_id += 1
        if len(to_be_processed) == 0: # unless current_children_list is also empty, current notde is refilled and loop continue
            to_be_processed = next_level
            parent_id = next_level_parent_id
            next_level_parent_id = []
            next_level = []
            level += 1
    return tree