Non-binary tree building

I have a lot of different inputs which I need to use to create some non-binary Trees. Each input has a <x,y> format, where x is the node value, and y is the number of children that specific node has. If the node is a '?', then it has children, if its a letter, then its a tree leave.

For example:

? 3
? 1
? 3
? 1
V 0
V 0
? 3
V 0
V 0
D 0
? 1
D 0
D 0
break

The first "?" is the root of the tree, and it has 3 children (which are the next 3 inputs). The, it the next 5 inputs are the children of those 3 nodes, and so on, the image above shows how to tree ends up.

I am using the class:

class NewNode():

def __init__(self, val):
    self.key = val
    self.child = []

I have stored all the pair inputs into a list, like so:

input_list = []
while True:
    inp = input().split()
    if inp == 'break':
        break
input_list.append(inp)

## this is the list for the example: [['?', '3'], ['?', '1'], ['?', '3'], ['?', '0'], ['V', '0'], ['V', '0'], ['?', '3'], ['V', '0'], ['V', '0'], ['D', '0'], ['?', '1'], ['D', '0'], ['D', '0']]

Now I am at the point where I'm trying to build the tree itself:

def build_the_tree(input_list):
    root = NewNode(input_list[0][0])  ## sets the root
    num_childs = int(input_list[0][1])
    input_list.pop(0)
    for i in(input_list):
        if i[0] == '?':           ## I am stuck at this point