# Data Structure – codewindow.in

## Related Topics ## Data Structure

1. #### In-order traversal: In this traversal, the left subtree is visited first, then the root node, and then the right subtree. This traversal is often used for binary search trees as it visits nodes in ascending order. In code, the in-order traversal can be implemented recursively as follows:

``````void inorderTraversal(TreeNode* root) {
if (root != nullptr) {
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
}
``````
1. #### Pre-order traversal: In this traversal, the root node is visited first, then the left subtree, and then the right subtree. This traversal is useful for creating a copy of the tree. In code, the pre-order traversal can be implemented recursively as follows:

``````void preorderTraversal(TreeNode* root) {
if (root != nullptr) {
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}
``````
1. #### Post-order traversal: In this traversal, the left subtree is visited first, then the right subtree, and then the root node. This traversal is useful for deleting the tree. In code, the post-order traversal can be implemented recursively as follows:

``````void postorderTraversal(TreeNode* root) {
if (root != nullptr) {
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val << " ";
}
}
``````

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

``````class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key

class BinarySearchTree:
def __init__(self):
self.root = None

def insert(self, key):
if self.root is None:
self.root = Node(key)
else:
self._insert(key, self.root)

def _insert(self, key, node):
if key < node.val:
if node.left is None:
node.left = Node(key)
else:
self._insert(key, node.left)
else:
if node.right is None:
node.right = Node(key)
else:
self._insert(key, node.right)

def search(self, key):
return self._search(key, self.root)

def _search(self, key, node):
if node is None or node.val == key:
return node
elif key < node.val:
return self._search(key, node.left)
else:
return self._search(key, node.right)

def delete(self, key):
self.root = self._delete(key, self.root)

def _delete(self, key, node):
if node is None:
return node

if key < node.val:
node.left = self._delete(key, node.left)
elif key > node.val:
node.right = self._delete(key, node.right)
else:
if node.left is None:
temp = node.right
node = None
return temp
elif node.right is None:
temp = node.left
node = None
return temp
else:
temp = self._min_value_node(node.right)
node.val = temp.val
node.right = self._delete(temp.val, node.right)
return node

def _min_value_node(self, node):
current = node
while current.left is not None:
current = current.left
return current

def inorder_traversal(self):
traversal = []
self._inorder_traversal(self.root, traversal)
return traversal

def _inorder_traversal(self, node, traversal):
if node is not None:
self._inorder_traversal(node.left, traversal)
traversal.append(node.val)
self._inorder_traversal(node.right, traversal)
``````

#### Therefore, maintaining a balanced binary tree with a relatively low height is important for achieving optimal performance in various operations on the tree. #### Questions on Chapter 7  #### Questions on Chapter 8  ## We Loveto Support you

Go through our study material. Your Job is awaiting.