Binary Tree Asking Game

How many of you reading remember the game Akinator? It was a game about a genie that guessed what you were thinking of through a series of yes or no questions. 

For instance, if you were thinking about a dog, the genie could have figured it out through asking the following questions:

“Is it a mammal?”

“Does it bark?”

“Is it a dog?”

And there he’d have the answer and find out what you were thinking of. 

I think I was about 10 when this game came out, and I remember being amazed at how the genie worked. Fast forward to today, I saw the app being recommended on my phone, and this led me to start thinking. How is this game implemented? After all, isn’t it just a a bunch of conditionals?

Well, it turns out to be nothing more than a binary tree implementation.

If you don’t know what a binary tree is, you might want to look them up before continuing. As a quick summary, it’s an object that has a value and two children (one child on the left and one child on the right – which themselves can also be trees).

From the example above, notice how 10 is the root (binary trees work upside down) and the parent of 5 and 19. Similarly, 5 is the parent of 1 and 6, and 19 is the parent of 17 and 21. 

Notice how values smaller than the parent go to the left. For instance, 5 is smaller than 10, so it’s on the left. Similarly, 1 is smaller than 5, so it’s to the left of 5. Likewise, notice how values larger than the parent go to the right. 19 is larger than 10, so it’s on the right. Finally, 21 is larger than 19, so it’s to the right of 19. 

So, how about we implement a question tree out of this? If the answer to a question is yes, we travel to the right. If the answer to a question is no, we travel to the left. 

And we keep asking them a question until we reach a leaf node. And when we then reach a leaf node, we ask the user if what they were thinking is equal to the leaf’s value. If it is, then we win. If not, we lose.

Let’s follow the example above. We start off by asking if the object is living. If the user answers no, we travel to the left. The left node is a leaf node, so that’s our last choice. We then ask the user, if it’s a door. If they answer yes, we guessed correctly. However, if they answer no, we were not able to guess it.

If we weren’t able to guess it, we’ll need to “learn” the new answer. We’ll learn it by having the user give us the answer and a question that’ll make it distinguishable from what we initially guessed. 

Let’s walk through the code logic:

First, we tell them we give up and then ask them what their guess was and then store it in the program somewhere. Let’s assume they say they thought of a car.

Next, we ask them for a yes or no question that would make it distinguishable from a car. Let’s say their question is: “Can you drive it?” and that the appropriate answer to that question is yes for what they were thinking and no for what we guessed (you can’t drive a door, can you?). 

Now, we ‘learn’ from this incident, and then add this to the tree. So, we replace our leaf door node and convert it to another parent tree with the question they gave us. We’ll add the no answer node to the left and the yes answer to the right.

The tree would now look like this:

Now, in our next game. If we ask them if it’s a living object and they say no, we travel to the left. Next, we ask if you can drive it. If they say no, we travel to the left again. Now, we ask if it’s a door. If they say yes, we win. If they answer no, we do the same thing as we did above by replacing the door node to be a question and extending door to be a child of the question.

So, let’s trying implementing this game ourselves. Here’s the plan:

• We’ll need to implement a super simple binary tree with a node class.
• Left children of the tree will be follow-ups to questions that are answered negatively.
• Right children of the tree will be follow-ups to questions that are answered positively.
• We keep traversing through the tree until we reach a leaf node.
• We’ll need to implement a medium for a user to interact with the binary tree.
• (Extra) We’ll finally serialize this information, so we don’t lose it the next time we run the program. 

And that’s it. Let’s get to work.

As always, let’s start with our Node class.

Binary Tree Implementation

class Node:
    """
    Simple binary tree node implementation.
    """
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

Our self.left variable will be what we traverse to if the question’s answer is no, and our self.right variable will be what we traverse to if the question’s answer is yes. Finally, our self.data variable will contain the question itself.

That’s all there is to the tree.

Moving on, let’s implement a medium for a user to interact with the tree.

Initial Medium Implementation

We’ll need to start off with some base question and yes or no answers to start the game. I’ll start with the question: Does it breathe? If the answer is yes, our guess will be a dog. If the answer is no, our guess will be a computer.

So, let’s code this. We basically just need to create a node with this question and two children nodes. The left child will contain the guess if the answer is no, and the right child will contain the guess if the answer is yes. In other words, left will contain computer, and right will contain dog.

In this implementation, I’ll define a function that’ll return the initial node:

def get_initial_node(
        question="Does it breathe?",
        noGuess="computer",
        yesGuess="dog") -> Node:
    """
    This function will return our initial node to begin the game with.
    :param question: Optional custom question to start game with. By default, it's "Does it breathe?".
    :param noGuess: Optional custom guess when answer is no to question. By default, it's computer.
    :param yesGuess: Optional custom guess when answer is yes to question. By default, it's dog.
    :return: Initial node with appropriate left and right children.
    """
    root = Node(question)
    root.left = Node(noGuess)
    root.right = Node(yesGuess)
    return root

The function comes with default values for the initial question and yes or no answers to it. It’s not hard-coded, so you can start the game with other questions. If you don’t want to bother with that, just stick with the function defaults. 

We create a root node with the question provided then set the left and right children respectively to the yes or no guesses.

Cool. Now, we have our first question and two guesses to start off the game. Let’s move on to start implementing the main game functions now.

Helper Functions

It’s usually a good programming habit to have small functions that perform one task. So, instead of doing everything in one huge function, let’s define some helper functions.

helper_get_answer_node() – function that’ll keep looping until the user types a valid answer. Once a valid answer is given, a node with that answer is returned.

def helper_get_answer_node() -> Node:
    """
    Helper function that prompts for user's answer.
    :return: Node with the answer encoded into it.
    """
    print("I can't guess it! What is it?")
    while True:  # Loop to make sure the answer has at least one character.
        answer = input(">>").lower()
        if len(answer) < 1:
            print("Please enter a valid answer with at least one character.")
            continue
        return Node(answer)  # Return the answer node.

helper_answered_yes() – function that’ll keep looping until the user types in yes or no. Returns true if user typed in yes, else False.

def helper_answered_yes() -> bool:
    """
    Helper function that prompts from a yes or no answer.
    :return: True if answer is yes, else False.
    """
    while True:
        answer = input(">>").lower()  # We'll ask for human input and lower-case the input.
        if len(answer) < 1 or answer[0] not in ('y', 'n'):  # If the user didn't provide a valid answer, ask again.
            print("I'm sorry. I couldn't quite understand that. Please type yes or no.")
            continue  # Repeat loop since the input was bad.

        if answer[0] == 'y':
            return True
        else:
            return False

helper_get_question_node(wrongNode) – a function that’ll keep looping until the user types in a valid question. Once the input is validated, it’ll return a node with the question. The argument wrongNode is passed to the function so that the user can see our incorrect guess.

def helper_get_question_node(wrongNode) -> Node:
    """
    Helper function that prompts for a question to what the user was guessing.
    :param wrongNode: The wrong node that we'll print to have user distinguish from it.
    :return: Node with the question encoded into it.
    """
    print(f"Please give me a yes or no question that distinguishes it from: {wrongNode.data}.")
    while True:  # Loop to make sure the user enters a valid question.
        question = input(">>").capitalize()
        if len(question) < 2 or question[-1] != "?":
            print("Please make sure you type a valid question. For example, 'Does it bark?' (without quotes)")
            continue
        return Node(question)

enter_question_and_answer(wrongNode) – a function that’ll modify the question node and set its respective children. If the question that they proposed defines what their answer is, the question’s right node will be the answer, and the question’s left node will be our initial guess. If the question that they proposed does not define what their answer is, the question’s right node will be our guess, and the question’s left node will be their answer.

Note that this function calls the functions we defined above. Also, note how the wrongNode is passed so that we can update the question node.

def enter_question_and_answer(wrongNode) -> Node:
    """
    We call this function at a stage where the node doesn't have an appropriate child node.
    :param wrongNode: The wrong node that will be modified.
    :return: New modified node with the new question and answer.
    """
    answerNode = helper_get_answer_node()
    questionNode = helper_get_question_node(wrongNode)

    print("Great! Is the answer to your question yes or no?")
    if helper_answered_yes():
        questionNode.right = answerNode
        questionNode.left = wrongNode
    else:
        questionNode.left = answerNode
        questionNode.right = wrongNode

    return questionNode

modify_node(childNode, parentNode, direction) – a function that’ll replace the leaf node with the new question node and its two guesses. Remember, this is a binary tree, so we’ll have to update the parent’s children references to reflect this change.

We have access to the parentNode, the childNode, and the direction, so this is easy.

def modify_node(childNode, parentNode, direction):
    """
    Modifies node in place.
    :param childNode: The child node that will be modified into a question.
    :param parentNode: Parent node that will update its reference.
    :param direction: Direction from the parent node that will change its reference.
    :return: None
    """
    if direction == 'left':
        parentNode.left = enter_question_and_answer(childNode)
    else:
        parentNode.right = enter_question_and_answer(childNode)

Main Game Loop

To reiterate, the game is nothing more than conditionals. So, when we start the game, we ask the initial question. If the answer to the question is yes, we traverse to the node’s right child. If the answer is no, we traverse to the node’s left child.  

Let’s take a look at the main function gameLoop():

def gameLoop(root):
    """
    Main game loop to traverse through the game.
    :param root: Parent root to start asking questions from.
    :return: Modified root with new answers (if entered).
    """
    copy = root  # Get a copy of the initial root node. We'll need this later.
    parent = None  # Keep track of the parent node when traversing.
    direction = None  # Keep track of the child node's direction from parent node.

    while root:  # Traverse through the root.
        if root.left == root.right:  # We reached a leaf node.
            print(f"Is it: {root.data}?")
            if helper_answered_yes():
                print("I win!")
            else:
                modify_node(root, parent, direction)  # Modify the leaf node and turn it into a question node.
            root = None  # Set root to None as the game is over.
        else:  # We reached a question node.
            print(root.data)
            parent = root
            if helper_answered_yes():
                direction = "right"
                root = root.right
            else:  # The user answered no to the question.
                direction = 'left'
                root = root.left

    return copy  # Return the parent node.

Let’s walk through the function. You pass a root tree to the function, then initialize the variable copy to be equal to the root. We’ll need this later when we return the modified tree for serialization (as this will be the top-most parent of all the nodes).

We set our parent and direction variables to None initially. The reason we need them is to update our child nodes. For instance, say we traverse to a leaf node and we guess wrong. We’ll have to update the parent node to modify its leaf child and convert it into a question node. 

Here’s an example: Notice how our door node is a leaf node.

Let’s speculate that the user answers that the object is not living, so we traverse to the left. We reach a leaf node, so we guess that it’s a door. It’s unfortunately not the right answer, so we ask for a question that’ll help us distinguish our guess from what the user’s answer is. Then, we’ll modify the leaf node into another tree node like so:

Other that than, all the function does is basically traverse through the tree until it reaches a leaf node. If it reaches a leaf node, it’ll call one of the helper functions and modify itself the same way as the example above does.

That’s about it really.

Main Game Function

We’re almost done. Now, we just need a play() function. The function will just call the helper function get_initial_node(), get its node, then pass that node to the gameLoop() function we defined above.

def play():
    while True:
        root = gameLoop(root)
        print("\nHurray! We have ended the game. Would you like to restart?")
        if helper_answered_yes():
            continue
        else:
            print("Goodbye.")
            break