Binary Search Tree

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

def sortedBST(arr):
    if not arr: 
        return None

    mid = int((len(arr))/2)
    root = Node(arr[mid])
    root.left = sortedBST(arr[:mid])
    root.right = sortedBST(arr[mid+1:])
    return root

    
    
def preOrder(node): 
    if not node: 
        return
      
    print (node.data)
    preOrder(node.left) 
    preOrder(node.right)  


arr = [1, 2, 3, 4, 5, 6, 7] 
root = sortedBST(arr) 
root
preOrder(root)     

class TreeNode:
    
    def __init__(self,key,val,left=None,right=None,parent=None):
        self.key = key
        self.payload = val
        self.leftChild = left
        self.rightChild = right
        self.parent = parent
        print("key {} payload {}".format(key,val))

    def hasLeftChild(self):
        return self.leftChild

    def hasRightChild(self):
        return self.rightChild

    def isLeftChild(self):
        return self.parent and self.parent.leftChild == self

    def isRightChild(self):
        return self.parent and self.parent.rightChild == self

    def isRoot(self):
        return not self.parent

    def isLeaf(self):
        return not (self.rightChild or self.leftChild)

    def hasAnyChildren(self):
        return self.rightChild or self.leftChild

    def hasBothChildren(self):
        return self.rightChild and self.leftChild

    def replaceNodeData(self,key,value,lc,rc):
        self.key = key
        self.payload = value
        self.leftChild = lc
        self.rightChild = rc
        if self.hasLeftChild():
            self.leftChild.parent = self
        if self.hasRightChild():
            self.rightChild.parent = self
            
    def findSuccessor(self):
        
        succ = None
        if self.hasRightChild():
            print("findSuccessor hasRightChild")
            succ = self.rightChild.findMin()
        else:
            if self.parent:
                
                if self.isLeftChild():
                    print("findSuccessor isLeftChild")
                    succ = self.parent
                else:
                    print("findSuccessor isRightChild")
                    self.parent.rightChild = None
                    succ = self.parent.findSuccessor()
                    self.parent.rightChild = self
        return succ
    
    def findMin(self):
        
        current = self
        while current.hasLeftChild():
            current = current.leftChild
        return current
    def spliceOut(self):
        print("spliceOut ")
        if self.isLeaf():
            print("isLeaf")
            if self.isLeftChild():
                print("isLeftChild")
                self.parent.leftChild = None
            else:
                print("rightChild")
                self.parent.rightChild = None
        elif self.hasAnyChildren():
            if self.hasLeftChild():
                print("hasLeftChild")
                if self.isLeftChild():
                    print("isLeftChild")
                    self.parent.leftChild = self.leftChild
                else:
                    print("isRightChild")
                    self.parent.rightChild = self.leftChild
                    self.leftChild.parent = self.parent
            else:
                print("else: ")        
                if self.isLeftChild():
                    print("isLeftChild")        
                    self.parent.leftChild = self.rightChild
                else:
                    print("isRightChild")
                    self.parent.rightChild = self.rightChild
                    self.rightChild.parent = self.parent
                
class BinarySearchTree:

    def __init__(self):
        self.root = None
        self.size = 0
        print("root {}".format(self.root))

    def length(self):
        return self.size

    def __len__(self):
        print("__len__ {}".format(self.size))
        return self.size

    def put(self,key,val):
        print("put key {} val {}".format(key,val))
        if self.root:
            self._put(key,val,self.root)
        else:
            self.root = TreeNode(key,val)
        self.size = self.size + 1

    def _put(self,key,val,currentNode):
        if key < currentNode.key:
            if currentNode.hasLeftChild():
                   self._put(key,val,currentNode.leftChild)
            else:
                   currentNode.leftChild = TreeNode(key,val,parent=currentNode)
        else:
            if currentNode.hasRightChild():
                   self._put(key,val,currentNode.rightChild)
            else:
                   currentNode.rightChild = TreeNode(key,val,parent=currentNode)

    def __setitem__(self,k,v):
        print("__setitem__ key {} val {}".format(k,v))
        self.put(k,v)

    def get(self,key):
        if self.root:
            res = self._get(key,self.root)
            if res:
                
                return res.payload
            else:
                return None
        else:
            return None

    def _get(self,key,currentNode):
        
        if not currentNode:
            return None
        elif currentNode.key == key:
            return currentNode
        elif key < currentNode.key:
            return self._get(key,currentNode.leftChild)
        else:
            return self._get(key,currentNode.rightChild)

    def __getitem__(self,key):
        print("__getitem__ {}".format(key))
        return self.get(key)

    def __contains__(self,key):
        print("__contains__ {}".format(key))
        if self._get(key,self.root):
            return True
        else:
            return False

    def delete(self,key):
        
        if self.size > 1:
            
            nodeToRemove = self._get(key,self.root)
            if nodeToRemove:
                self.remove(nodeToRemove)
                self.size = self.size-1
            else:
                raise KeyError('Error, key not in tree')
        elif self.size == 1 and self.root.key == key:
            self.root = None
            self.size = self.size - 1
        else:
            raise KeyError('Error, key not in tree')

    def __delitem__(self,key):
        
        self.delete(key)

#     def spliceOut(self):
#         print("spliceOut ")
#         if self.isLeaf():
#             print("isLeaf")
#             if self.isLeftChild():
#                 print("isLeftChild")
#                 self.parent.leftChild = None
#             else:
#                 print("rightChild")
#                 self.parent.rightChild = None
#         elif self.hasAnyChildren():
#             if self.hasLeftChild():
#                 print("hasLeftChild")
#                 if self.isLeftChild():
#                     print("isLeftChild")
#                     self.parent.leftChild = self.leftChild
#                 else:
#                     print("isRightChild")
#                     self.parent.rightChild = self.leftChild
#                     self.leftChild.parent = self.parent
#         else:
#             print("else: ")        
#             if self.isLeftChild():
#                 print("isLeftChild")        
#                 self.parent.leftChild = self.rightChild
#             else:
#                 print("isRightChild")
#                 self.parent.rightChild = self.rightChild
#                 self.rightChild.parent = self.parent

#     def findSuccessor(self):
        
#         succ = None
#         if self.hasRightChild():
#             print("findSuccessor hasRightChild")
#             succ = self.rightChild.findMin()
#         else:
#             if self.parent:
                
#                 if self.isLeftChild():
#                     print("findSuccessor isLeftChild")
#                     succ = self.parent
#                 else:
#                     print("findSuccessor isRightChild")
#                     self.parent.rightChild = None
#                     succ = self.parent.findSuccessor()
#                     self.parent.rightChild = self
#         return succ

#     def findMin(self):
        
#         current = self
#         while current.hasLeftChild():
#             current = current.leftChild
#         return current

    def remove(self,currentNode):
        
        if currentNode.isLeaf(): #leaf
            if currentNode == currentNode.parent.leftChild:
                currentNode.parent.leftChild = None
            else:
                currentNode.parent.rightChild = None
        elif currentNode.hasBothChildren(): #interior
            
            succ = currentNode.findSuccessor()
            succ.spliceOut()
            currentNode.key = succ.key
            currentNode.payload = succ.payload

        else: # this node has one child
            if currentNode.hasLeftChild():
                if currentNode.isLeftChild():
                    currentNode.leftChild.parent = currentNode.parent
                    currentNode.parent.leftChild = currentNode.leftChild
                elif currentNode.isRightChild():
                    currentNode.leftChild.parent = currentNode.parent
                    currentNode.parent.rightChild = currentNode.leftChild
                else:
                
                    currentNode.replaceNodeData(currentNode.leftChild.key,
                                    currentNode.leftChild.payload,
                                    currentNode.leftChild.leftChild,
                                    currentNode.leftChild.rightChild)
            else:
                
                if currentNode.isLeftChild():
                    currentNode.rightChild.parent = currentNode.parent
                    currentNode.parent.leftChild = currentNode.rightChild
                elif currentNode.isRightChild():
                    currentNode.rightChild.parent = currentNode.parent
                    currentNode.parent.rightChild = currentNode.rightChild
                else:
                    currentNode.replaceNodeData(currentNode.rightChild.key,
                                    currentNode.rightChild.payload,
                                    currentNode.rightChild.leftChild,
                                    currentNode.rightChild.rightChild)




mytree = BinarySearchTree()
mytree[20] = 20
mytree[5] = 5
mytree[25] = 25
mytree[3] = 3
mytree[10] = 10
mytree[23] = 23
mytree[29] = 29
mytree[7] = 7
mytree[12] = 12
mytree[15] = 15
mytree[13] =13
mytree[17] = 17

del mytree[10]

Binary Search Tree

• return all left ,right children node value
  ```python leftbuf = [] rightbuf = [] treevals = [] def tree_seq(Node,root): if Node is None: return [] if Node.data < root.data: leftbuf.append(Node.data) if Node.data > root.data : rightbuf.append(Node.data)

  tree_seq(Node.left,root) tree_seq(Node.right,root)

  print(leftbuf,rightbuf)

  return Node.data

def tree_seq2(Node,root): if Node is None: return [] if Node.data < root.data: leftbuf.append(Node.data) if Node.data > root.data : rightbuf.append(Node.data)

tree_seq2(Node.left,Node)
tree_seq2(Node.right,Node)

print(leftbuf,rightbuf) #     return Node.data ```