Binary Tree move left XOR right exactly one node at a time

Question

I want to "walk" though a binary tree, depending on user input. e.g., if answer no then move one node down to the left. If yes move one node down to the right. Kinda like a 20 questions game

class Node:
    
    def __init__(self, data):
        
        self.left = None
        self.right = None
        self.data = data
  
        
    def insert(self, data):
        
        #compare if left none insert, otherwiese rigt 
       # Compare the new value with the parent node
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data
    # Print the tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()

How to move around

def move(text):
    if text == 'y':
        print('move right')

    else:
        print('move left')
       
        
def menu(choices):
    ans = 'NONE'
   
    for i in theNodes:
        text = input("Please select y xor n: ")
        move(text)
        ans = i
        print(ans)
        
        
        if ans in endNode:
            break
        
            
print('You position ' + ans)

theNodes = ['A','B','C','D','E' ,'F', 'G']
endNode = 'EDFG'

How can you move around a tree structure, one node at a time?

fshabashev · Accepted Answer · 2021-07-07T22:51:46.340

Let's take 20 questions game as an example.

In the 20 questions game you need to traverse your binary tree based on the user input and always keep in mind where you are in the tree at any given moment.

To implement this you need a data structure that can memorise your current location in the tree.

You can implement this data structure like this:

class TreeCursor:
    node = None

    def __init__(self, root):
        self.node = root
    
    def move_left(self):
        self.node = self.node.left

    def move_right(self):
        self.node = self.node.right

With that data structure you can implement the tree traversal like this:

N_QUESTIONS = 20 # number of questions you want to ask

def traverse_tree(tree_cursor):
    for i_question in range(N_QUESTIONS):
        text = input("Please select y xor n: ")
        if text == 'y':
            tree_cursor.move_right()
        elif text == 'n':
            tree_cursor.move_left()

Now let's say you have created a binary tree and you want to traverse it. Let's create a binary tree and traverse it.

This is how you can do it. Here is how you can create the tree:

tree = Node('A')
tree.left = Node('B')
tree.right = Node('C')

Here is how you can traverse the tree we created on the previous step:

tree_cursor = TreeCursor(tree)
traverse_tree(tree_cursor)

Thanks! TreeCursor(object) is this object the binary tree, which I have created earlier? Or is it meant as, I need to work with TreeCursor to implement " def insert" functions ect.? — MisterIvan, Jul 07 '21 at 16:42
in this case TreeCursor(object) means that TreeCursor class inherits from the object. This is an outdated syntax from python2.7. I wrote it this way by force of habit. You can read more here: https://stackoverflow.com/questions/4015417/why-do-python-classes-inherit-object Let me add some more examples to the answer. — fshabashev, Jul 07 '21 at 21:26

Binary Tree move left XOR right exactly one node at a time

1 Answers1