What is the difference between a binary tree and a binary search tree?
A binary tree is any tree where each node has at most two children, with no rule about their values. A binary search tree adds an ordering rule, where every left child is smaller than its parent and every right child is larger. That ordering is what makes searching in a binary search tree fast, on average O(log n).
- A binary tree only limits each node to at most two children, with no ordering rule.
- A binary search tree adds the rule that left values are smaller and right values are larger.
- A BST is fast only when balanced, since sorted inserts turn it into a slow O(n) chain.
Binary tree
This is just a shape rule. Each node points to at most a left and a right child. Values can be arranged in any way, so there is no fast way to search it in general.
Binary search tree
This adds meaning to the arrangement. Smaller values go left and larger values go right. Because of this you can skip half the tree at each step while searching, just like binary search on an array.
# BST property at every node:
# left subtree values < node value
# right subtree values > node value
#
# 8
# / \
# 3 10
# / \ \
# 1 6 14Be ready for the catch that a binary search tree is only fast when balanced. If you insert sorted data it becomes a straight line and searching drops to O(n). Mentioning balanced trees like AVL or red black trees to fix this shows depth.
Frequently asked questions
What happens to a BST if you insert sorted data?
It becomes a straight line, like a linked list, so search drops from O(log n) to O(n). Balanced trees like AVL or red black trees prevent this.
What are tree traversals?
They are orders for visiting nodes. Inorder on a BST gives sorted output, preorder visits the root first, and postorder visits the root last.
Common follow up questions
Related interview questions
Want the full DSA guide?
Read every DSA concept with notes, diagrams, and code in one place. Track your progress as you go.
Open the DSA guide All DSA questions