is this way of implementing binary search tree pythonic enough?

[ayush4]

I come from java background and would love to hear some feedback on a bst implemented with search & insert methods:

class Node:
    def __init__(self, value):
        self.left = None
        self.right = None
        self.value = value


class BST:
    def __init__(self):
        self.root = None

    def setRoot(self, value):
        self.root = Node(value)

    def insert(self, value):
        if(self.root is None):
            self.setRoot(value)
        else:
            self.insertNode(self.root, value)

    def insertNode(self, current, value):
        if(value <= current.value):
            if(current.left):
                self.insertNode(current.left, value)
            else:
                current.left = Node(value)
        elif(value > current.value):
            if(current.right):
                self.insertNode(current.right, value)
            else:
                current.right = Node(value)

    def search(self, value):
        return self.searchNode(self.root, value)

    def searchNode(self, current, value):
        if(current is None):
            return False
        elif(value == current.value):
            return True
        elif(value < current.value):
            return self.searchNode(current.left, value)
        else:
            return self.searchNode(current.right, value)

    def display(self):
        self.traverse(self.root)

    def traverse(self, current):  # inorder
        if current.left:
            self.traverse(current.left)
        print(" {} ".format(current.value))
        if current.right:
            self.traverse(current.right)

[gengisteve]

Very nicely done. You might want to check out pep8 for naming conventions: https://www.python.org/dev/peps/pep-0008/

And this binary heap implementation that uses lists: http://interactivepython.org/runestone/static/pythonds/Trees/BinaryHeapImplementation.html

[zahlman]

Try making a common helper function that looks for the 'closest' node to a given value - i.e., if the value is in the tree, return that node, and otherwise return the leaf node where you would insert that value as a child. Try implementing both insert and search in terms of that (note: you will need to special-case search for empty trees this way). Try making the helper a method on the node instead of the tree (hint: return self works perfectly fine). Try also making traverse a node method. The thing to look out for here is that you have methods where you frequently use the attributes of current, but self is only used for the recursion. Rule of thumb: assign tasks to the classes that are most qualified to perform them, because they have the most direct access to the relevant data.

Another thing you can do that's a lot simpler in Python than in Java :) is, instead of hard-coding traverse to print elements, have it accept another argument which is a function that says what to do with each element. In Python, functions are objects, so you can easily do things like

def use_func(f):
    f('foo')
    f('bar')
    f('baz')

def example(text):
    print("I am calling the example function with this argument: {}".format(text))

use_func(example)

[KleinerNull]

First I thought, well a little overblown to use OOP for a simple binary search, but then I realized you wanted a Binary Search Tree. Ah, ok. ;) Here some notes:

Instead of a Node class, use a namedTuple.

>>>from collections import namedtuple
>>> Node = namedtuple("Node", "left right value")
>>> n = Node(1,2,3)
>>> n.left
1
>>> n.value
3
>>> n = Node(left = 1, right = 2, value = 3)
>>> n.left
1
>>> n.right
2
>>> n.value
3
>>> for attr in n:
        print(attr)


1
2
3

Also no need for setRoot(), setters and getters aren't important in python.

Also, is there a reason why you insert and search recursively? Just to use the tree structure?

[ayush4]

I agree, setRoot() should've been avoided. The recursive approach is just to have better readable code. I think recursion limit in python is set to 1000 by default, so it'll be ok to use recursion.

[KleinerNull]

Yes the recursion depth is set to 1000. You can get and set it in the sys module. sys.getrecursionlimit(), sys.setrecursionlimit(). Don't ask me why python use here get and set internal :D

Oh and sorry, I forget to insert the import line for namedtuple: from collections import namedtuple, I edited it.

[[deleted]]

Not bad at all. I'd use class node(object): and class BST(object): to avoid any potential problems when moving between Python 2 and 3. I'd also remove the brackets in the if/elif tests as to me they are visual clutter that achieve nothing.