Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
a simple implementation of a Binary Search Tree in Python
class Node:
def __init__(self, val):
self.val = val
self.leftChild = None
self.rightChild = None
def get(self):
return self.val
def set(self, val):
self.val = val
def getChildren(self):
children = []
if(self.leftChild != None):
children.append(self.leftChild)
if(self.rightChild != None):
children.append(self.rightChild)
return children
class BST:
def __init__(self):
self.root = None
def setRoot(self, val):
self.root = Node(val)
def insert(self, val):
if(self.root is None):
self.setRoot(val)
else:
self.insertNode(self.root, val)
def insertNode(self, currentNode, val):
if(val <= currentNode.val):
if(currentNode.leftChild):
self.insertNode(currentNode.leftChild, val)
else:
currentNode.leftChild = Node(val)
elif(val > currentNode.val):
if(currentNode.rightChild):
self.insertNode(currentNode.rightChild, val)
else:
currentNode.rightChild = Node(val)
def find(self, val):
return self.findNode(self.root, val)
def findNode(self, currentNode, val):
if(currentNode is None):
return False
elif(val == currentNode.val):
return True
elif(val < currentNode.val):
return self.findNode(currentNode.leftChild, val)
else:
return self.findNode(currentNode.rightChild, val)
@lconnell

This comment has been minimized.

Copy link

@lconnell lconnell commented Jun 2, 2017

Thanks for the easy and straight forward example!

@leandrotk

This comment has been minimized.

Copy link

@leandrotk leandrotk commented Jun 28, 2017

Thanks for this implementation! :)

Just two comments:

  1. Python uses underscore as method and variable naming: find_node, left_children, ...

  2. Maybe the setRoot needs to be a private method. If we insert 5 new nodes, and then call setRoot method, it will clear all nodes we inserted. It is not a problem we want to handle.

Great work! 👍

@ahamdabo

This comment has been minimized.

Copy link

@ahamdabo ahamdabo commented Jul 19, 2017

Straight forward implementation. However, the insert function shall be updated to ignore adding redundant values.

@manjitha27

This comment has been minimized.

Copy link

@manjitha27 manjitha27 commented Oct 20, 2017

can you make delete function
part for this

@leobotler

This comment has been minimized.

Copy link

@leobotler leobotler commented Aug 8, 2019

Thanks!

@arsaltariq

This comment has been minimized.

Copy link

@arsaltariq arsaltariq commented Dec 30, 2019

Thanks, it helped me.

@RamonWill

This comment has been minimized.

Copy link

@RamonWill RamonWill commented Jan 20, 2020

Thank you very much

@shree675

This comment has been minimized.

Copy link

@shree675 shree675 commented Jun 1, 2020

Could you please show how deletion is done?

@rakaar

This comment has been minimized.

Copy link

@rakaar rakaar commented Sep 14, 2020

For deletion, the function in Node class would be

def delete(self):
        # cases where the node is a leaf, just remove it
        if self.leftNode == None and self.rightNode == None:
            if self.parent.value > self.value:
                self.parent.rightNode = None
            else:
                self.parent.leftNode = None
            # remove parent's Link
            self.parent = None
            return

        # cases where children are only in one direction, just change the pointers
        # where children only in left direction
        if self.rightNode == None:
            self.parent.leftNode = self.leftNode
            self.leftNode.parent = self.parent

            self.parent = None
            self.leftNode = None
            return
        # where children only in rightdirection
        elif self.leftNode == None:
            self.parent.rightNode = self.rightNode
            self.rightNode.parent = self.parent

            self.parent = None
            self.leftNode = None
            return

        
        # cases where there are children in both the directions
        # swap values between currentNode and its succesorNode
        # delete the successor_node(which contains the value to be removed from tree), note that the successor_node is a leaf
        successor_node = self.rightNode.find_min_in_sub_tree()
        successor_node.value, self.value = self.value, successor_node.value
        successor_node.delete()

not easy part: why self.rightNode.find_min_in_sub_tree() was done. The reason behind doing this is to find its next biggest value(its successor) in the tree

the implementaion of find_min_in_sub_tree. This function finds the minimum element in the tree below it, by continuously looking at the left

def find_min_in_sub_tree(self):
        if self.leftNode == None:
            return self
        
        if self.leftNode != None:
            return self.leftNode.find_min_in_sub_tree()

Reference

@shree675, @manjitha27
Do let me know if something is wrong

EDIT- Thanks to @Aniket2ten96 for pointing out the mistake

@Aniket2ten96

This comment has been minimized.

Copy link

@Aniket2ten96 Aniket2ten96 commented Sep 29, 2020

@rakaar I think the code to find the successor_node might not yield the correct result. Suppose a bst rooted at 69, and its right side nodes are 70,82,84. Now I want to find 69's successor, according to your code i will go to right and i will find the node with maximum key and that will be the successor of 69. In the above example the maximum key is 84, which is not the successor of 69(successor of 69 is 70 in the above example) . I think to find the successor, you have to go right and find the node with minimum key value, which is in the above example 70. Correct me if I am wrong

@rakaar

This comment has been minimized.

Copy link

@rakaar rakaar commented Sep 29, 2020

Thanks a lot @Aniket2ten96 for pointing it out
I have made the changes
You are right, it should be finding out the minimum in the subtree where self.rightNode acts as the root. Hence replaced the wrong function with find_min_in_sub_tree along with its implementation

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment