Python: Binary Search Tree – BST

Python

Video is ready, Click Here to View ×


How to write a Binary Search Tree program in Python 3, including insert, find, preorder, postorder, and inorder traversal functions, with example BST code implementation. Get the code, which includes the remove function, from my github site here:
www.github.com/joeyajames/Python

31 thoughts on “Python: Binary Search Tree – BST

  1. Hi Joe Thanks for the great video on BST,
    I have one doubt tho, at 1.50-2.00 you mentioned that insert is now called on the root node which is in the Node class. But i am seeing the root node defined in Tree class and not in Node class. Please explain where I am getting this wrong. Thanks a lot in advance!! 😀

  2. why return self.rightchild.insert? why not just self.rightchild.insert ? We aren't returning a value we just want the recusion of the function. that return statement is throwing me

  3. Hi Joe! I am having doubt in code line number 19 (insert function called recursively) since there are 2 insert functions one in node class and other one in tree class. how will this insert function refers to node class?. any help is highly appreciated ! Thanks in advance

  4. how to implement this
    Tasks:
    Implement a binary search tree

    class BSTree(object):
    ''' Implement a binary search tree.

    Each method you need to implement has its own docstring
    with further instruction. You'll want to move most of the
    implementation details to the Node class below.

    Additionally, keep count of the total number of Trees created
    and the number of Nodes in each tree. Include a class method,
    "num_trees" to return the former.
    '''

    def _init_(self):
    pass

    def _str_(self):
    ''' Return a representation of the tree as ({left} {elem} {right})
    where elem is the element stored in the root, and left and right
    are the left and right subtrees (which print out similarly).
    Empty trees should be represented by underscores.
    '''
    pass

    def _len_(self):
    ''' Returns the number of nodes in the tree.'''
    pass

    def _contains_(self, element):
    ''' Finds whether a given element is in the tree.
    Returns True if the element is found, else returns False.
    '''

    def insert(self, element):
    ''' Insert a given value into the tree.
    Our implementation will allow duplicate nodes. The left subtree
    should contain all elements <= to the current element, and the
    right subtree will contain all elements > the current element.
    '''
    pass

    def elements(self):
    ''' Return a list of the elements visited in an inorder traversal:
    http://en.wikipedia.org/wiki/Tree_traversal
    Note that this should be the sorted order if you've inserted all
    elements using your previously defined insert function.
    '''
    pass

    class Node(object):
    ''' A Node of the BSTree.
    Important data attributes: value (or element), left and right.
    '''
    pass

    def main():
    pass

    if _name_ == "__main__":
    main()

  5. How do you find a number of a "visited" nodes? Let's say it travels through few nodes and I need to make a function that tells me how many nodes (paths) it took to get there. Also I need to find a minimum and maximum of these path (or should I say levels?)

    Anyway thank you for this video, it ACTUALLY help me understand it.

Leave a Reply

Your email address will not be published. Required fields are marked *