Data Structure – codewindow.in

Data Structure

Here's an example implementation of a binary search tree in Python:

``````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)
``````

In-order traversal: In an in-order traversal, the left subtree is visited first, then the current node, and finally the right subtree. This produces a sorted list of the tree's nodes in ascending order. Here is an example of in-order traversal implemented in Python:

``````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)
``````

We Loveto Support you

Go through our study material. Your Job is awaiting.