A Binary Search Tree (BST) is a binary tree where each node follows the following properties:
- The left child contains only nodes with values less than the parent node.
- The right child contains only nodes with values greater than the parent node.
- Both the left and right subtrees must also be binary search trees.
Why is it Called a Search Tree?
It is called a “Search Tree” because it allows efficient search operations using the tree structure. If the tree is balanced, searching has a time complexity of:
O(log n)
Inorder Traversal
If we perform an inorder traversal (left → node → right), the values we get are in sorted order.
Example Tree:
50
/ \
30 70
/ \ / \
20 40 60 80
/ \ / \ / \
10 25 35 45 75 85
Inorder Traversal: 10 20 25 30 35 40 45 50 60 70 75 80 85 (Sorted)
Time & Space Complexity
- Search (Balanced BST):
O(log n) - Traversal:
O(n) - Space:
O(h)(Recursive call stack, where h = height)
// Inorder Traversal of BST
function inorderTraversal(root) {
if (!root) return;
inorderTraversal(root.left);
console.log(root.val);
inorderTraversal(root.right);
}
void inorderTraversal(TreeNode* root) {
if (!root) return;
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
void inorderTraversal(struct TreeNode* root) {
if (root == NULL) return;
inorderTraversal(root->left);
printf("%d ", root->val);
inorderTraversal(root->right);
}
void inorderTraversal(TreeNode root) {
if (root == null) return;
inorderTraversal(root.left);
System.out.print(root.val + " ");
inorderTraversal(root.right);
}
def inorderTraversal(root):
if not root:
return
inorderTraversal(root.left)
print(root.val)
inorderTraversal(root.right)
void InorderTraversal(TreeNode root) {
if (root == null) return;
InorderTraversal(root.left);
Console.Write(root.val + " ");
InorderTraversal(root.right);
}
