Related Topics
Data Structure
void inorderTraversal(TreeNode* root) {
if (root != nullptr) {
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
}
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);
}
}
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 << " ";
}
}
In all of these traversals, the base case is when the root node is null.
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)
Popular Category
Topics for You
Go through our study material. Your Job is awaiting.