CODEWITHSUNDEEP
pythonbinary-search-treepreorder
paparonnie
paparonnie

Reputation: 170

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)

Upvotes: 0

Views: 1222

Answers (1)

GAVD
GAVD

Reputation: 2134

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)

Upvotes: 0

Related Questions