Custom binary tree object in Python

Question

I'm trying to write a custom binary tree class. I already have the node:

class Node:

def __init__(self, value, **kwargs):
    self.value = value
    self.kwargs = kwargs

    for key, value in kwargs.items():
        setattr(self, key, value)

def __str__(self):
    main_str = '{value: ' + str(self.value)
    for key, value in self.kwargs.items():
        main_str += ', ' + str(key) + ': ' + str(value)
    main_str += '}'

    return main_str

The node uses kwargs because i'm using it also for other things. The problem i'm having is in the tree class:

from models.node import Node
class BinarySearchTree:

    def __init__(self):
        self.root = None

    def add_element(self, value):
        node = Node(value, left=None, right=None)

        if not self.root:
            self.root = node

        else:
            self.__add_element_recursive(self.root, value)

    def __add_element_recursive(self, parent, value):

        if not parent:
            node = Node(value, left=None, right=None)
            parent = node

        elif value > parent.value:
            self.__add_element_recursive(parent.right, value)

        else:
            self.__add_element_recursive(parent.left, value)

This clearly doesn't work because the parameters in python don't get passed as references but as new instances. For example, I know this would work in C++ because I can just pass pointers to the methods.

How do I create the method to add a value to the tree? I think I might be missing something really obvious here.

It's not clear what you mean by This clearly doesn't work because the parameters in python don't get passed as references but as new instances. If you pass a Node instance as a parameter, the function will receive a reference to that Node not a copy or new instance.. — Mark
– Mark, Commented May 27, 2019 at 0:45

Sandalaphon · Accepted Answer · 2019-05-27 01:14:30Z

1

You need to attach the created node to a branch of the tree.

try this:

def __add_element_recursive(self, parent, value):
    if value > parent.value:
        if parent.right: # there's a right node: lets go there
            self.__add_element_recursive(parent.right, value)
        else: # No node: we have found our spot
            parent.right = Node(value, left=None, right=None)
    elif parent.left: # There's a left node...lets go there
        self.__add_element_recursive(parent.left, value)
    else: # No node: we have found our spot
        parent.left = Node(value, left=None, right=None)

edited May 27, 2019 at 1:14

answered May 27, 2019 at 0:59

Sandalaphon

1549 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Custom binary tree object in Python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related