Related Topics
Data Structure
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, val):
if not self.root:
self.root = TreeNode(val)
return
curr = self.root
while True:
if val < curr.val:
if not curr.left:
curr.left = TreeNode(val)
break
curr = curr.left
else:
if not curr.right:
curr.right = TreeNode(val)
break
curr = curr.right
def search(self, val):
curr = self.root
while curr:
if val == curr.val:
return True
elif val < curr.val:
curr = curr.left
else:
curr = curr.right
return False
def delete(self, val):
def get_min(node):
while node.left:
node = node.left
return node
def remove(node, val):
if not node:
return None
if val == node.val:
if not node.left and not node.right:
return None
if not node.left:
return node.right
if not node.right:
return node.left
temp = get_min(node.right)
node.val = temp.val
node.right = remove(node.right, temp.val)
elif val < node.val:
node.left = remove(node.left, val)
else:
node.right = remove(node.right, val)
return node
self.root = remove(self.root, val)
This implementation has three methods:
insert: adds a node with the given value to the tree, maintaining the binary search tree propertysearch: returnsTrueif a node with the given value is in the tree,Falseotherwisedelete: removes the node with the given value from the tree, maintaining the binary search tree property
The TreeNode class represents a node in the binary search tree, with a val attribute for the node’s value and left and right attributes for the node’s left and right child nodes, respectively. The BinarySearchTree class represents the binary search tree as a whole, with a root attribute for the root node.
The insert method works by traversing the tree from the root node, moving left or right depending on whether the value to be inserted is less than or greater than the current node’s value, respectively. When it reaches a leaf node, it adds the new node as its left or right child, depending on the value to be inserted.
The search method works in a similar way, traversing the tree from the root node until it finds a node with the given value or reaches a leaf node without finding the value.
The delete method is a bit more complicated. It works by recursively traversing the tree to find the node with the given value, and then removing it in a way that maintains the binary search tree property. If the node to be removed is a leaf node, it is simply deleted. If it has only one child, that child takes its place. If it has two children, the node’s value is replaced with the value of its right child’s minimum value (i.e., the leftmost node in the right subtree), and then that node is removed instead.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorder_traversal(root):
if root:
inorder_traversal(root.left)
print(root.val)
inorder_traversal(root.right)
Pre-order traversal: In a pre-order traversal, the current node is visited first, then the left subtree, and finally the right subtree. Here is an example of pre-order traversal implemented in Python:
def preorder_traversal(root):
if root:
print(root.val)
preorder_traversal(root.left)
preorder_traversal(root.right)
Post-order traversal: In a post-order traversal, the left subtree is visited first, then the right subtree, and finally the current node. Here is an example of post-order traversal implemented in Python:
def postorder_traversal(root):
if root:
postorder_traversal(root.left)
postorder_traversal(root.right)
print(root.val)
Popular Category
Topics for You
Go through our study material. Your Job is awaiting.