pythonbinary-search-treepreorder

Binary Search Tree with user inputted data


I'm trying to create a binary search tree where the user can input data into the main(), where the first number will be the root, and the rest will be sorted and printed into pre-order from there. Python.

I'm new to this, and am pretty lost. So far, it's making the user input data twice, and it won't do the insert function (keeps giving me attribute errors). I've tried numerous ways of approaching this, but I'm getting to a point where it feels like I'm just guessing. Any help would be greatly appreciated.

Here is what I have so far:

class Node:
    def __init__(self, key):
        self.key = key
        self.leftBranch = None
        self.rightBranch = None

def insert(root, key):
    if root is None:
        root = main().keys[0]
        return root
    else:
        if root.key == key:
            return root
        elif root.key < key:
            root.rightBranch = insert(root.rightBranch, key)
        else:
            root.leftBranch = insert(root.leftBranch, key)
    return root

def preorder(root):
    if root:
        print(root.key)
        preorder(root.leftBranch)
        preorder(root.rightBranch)
    
def main():
    keys = input('Enter data to construct a BST (numbers divided by a space): ').split(' ')

    for key in keys:
        return key

 
Node(main())
r = insert(main().keys[0], main().key)
preorder(r)

Solution

  • Your code has several problem.

    1. You call main() too much. Whenever you call main(), it requests you to give an array.

    2. You split input wrong. I guess you want to make BST with int. You can do like this.

    keys = list(map(int,input('Enter data to construct a BST (numbers divided by a space): ').split()))
    
    1. Your insert function has issues. You don't check leftBranch and rightBranch exists or not. You should add new value in left before right.

    Code example.

    class Node:
        def __init__(self, key):
            self.key = key
            self.leftBranch = None
            self.rightBranch = None
    
    def insert(root, key):
        if root is None:
            root = Node(key)
            return
        else:
            if root.key == key:
                return
            
            if key < root.key:
                if root.leftBranch:
                    insert(root.leftBranch, key)
                    return
                root.leftBranch = Node(key)
                return
            
            if root.rightBranch:
                insert(root.rightBranch, key)
                return
            root.rightBranch = Node(key)
        
    
    def preorder(root):
        if root:
            print(root.key)
            preorder(root.leftBranch)
            preorder(root.rightBranch)
        
    
    keys = list(map(int,input('Enter data to construct a BST (numbers divided by a space): ').split()))
    print(keys)
    
    root = Node(keys[0])
    
    for key in keys:
        insert(root, key)
    
    preorder(root)