Binary Tree vs Binary Search Tree in Java — Properties, Complexity, Use Cases

Binary tree vs BST — the difference

Binary tree

• Each node has at most 2 children
• No ordering constraint
• Just a structural concept

Binary search tree (BST)

• Binary tree + BST property
• Left subtree all < node
• Right subtree all > node

The defining property of BST

• In-order traversal yields sorted output
• (left, node, right) recursively → ascending order

Operations

Binary tree

• Search: O(n) — must check every node
• Insert/delete: O(1) given position, O(n) to find
• Used when structure matters, not order

BST

• Search/insert/delete: O(log n) average
• O(n) WORST CASE if skewed
• Predecessor/successor: O(log n) avg
• Range query: O(log n + k)

The skew problem

• Insert sorted data 1,2,3,4,5 into plain BST
• All right children → linked list
• Operations degrade to O(n)
• Solution: self-balancing trees

Self-balancing BSTs

AVL

• Strict balance (height diff ≤ 1)
• Faster lookups
• More rotations on writes

Red-Black

• Looser balance (height ≤ 2 log n)
• Fewer rotations on writes
• Mixed workloads
• Java's choice for TreeMap, TreeSet

B-tree / B+ tree

• Multi-way, not binary
• Disk-resident data
• Databases (PostgreSQL, MySQL indexes)

Splay tree

• Recently-accessed moves to root
• Amortized O(log n)
• Caches

Java built-ins

No plain binary tree — implement yourself

class Node { int val; Node left, right; }

TreeMap / TreeSet — Red-Black BST

• O(log n) all operations
• Range queries: ceilingKey, floorKey, subMap
• Sorted iteration

HashMap (treeified buckets) — since Java 8

• Bucket has linked list normally
• Converts to Red-Black tree when bucket size > 8
• Mitigates worst-case hash collisions

PriorityQueue — binary heap

• Special complete binary tree
• O(1) peek, O(log n) insert/extract
• For min/max access only, not full order

Use cases

Plain binary tree

• Expression trees: (a+b)*c
• Decision trees
• File hierarchies
• Huffman coding
• Heaps (special case)
• Abstract syntax trees
• Game trees (minimax)

BST (TreeMap/TreeSet)

• Ordered storage
• Range queries
• Sorted iteration
• Worst-case O(log n) guarantees

HashMap

• Unordered O(1) avg
• No range queries
• Faster than TreeMap for lookups

LinkedHashMap

• O(1) avg + insertion order
• LRU cache

PriorityQueue

• Min/max access only
• Dijkstra, top-K, scheduling

Decision matrix

• Order + range queries → TreeMap
• Order + insertion order → LinkedHashMap
• Lookup speed only → HashMap
• Min/max only → PriorityQueue
• Hierarchical data → plain binary tree

Tree shapes

Full binary tree

• Every node has 0 or 2 children

Complete binary tree

• All levels full except possibly last
• Last level filled left-to-right
• Heaps are complete

Perfect binary tree

• All internals have 2 children
• All leaves at same depth

Balanced binary tree

• Left and right subtree heights differ by ≤ 1

Common bugs

1. Not balancing

• Plain BST + sorted input → O(n)
• Use TreeMap, not custom BST

2. Confusing binary tree with BST

• Binary tree has no order
• BST has order

3. Forgetting in-order traversal property

• BST in-order = sorted output
• Use this to validate a BST or to sort

4. Implementing delete incorrectly

• Three cases: leaf, one child, two children
• For two children: replace with in-order successor

5. Not knowing TreeMap is Red-Black

• It's not just 'a sorted map' — it's a Red-Black tree
• O(log n) worst case guaranteed

For interviews

• Define binary tree vs BST clearly
• Mention in-order traversal yields sorted output
• Discuss skew → self-balancing
• Address Java's TreeMap as Red-Black
• Contrast with HashMap (no order, O(1) avg)

Recommendation: A binary tree is any tree where each node has at most 2 children — no ordering constraint, used for hierarchical structures like expression trees, decision trees, file systems, Huffman coding, heaps, and ASTs. A binary search tree (BST) adds the BST property (left < node < right), making search/insert/delete O(log n) average — but O(n) worst case if the tree degenerates into a chain (sorted input is the classic trigger). The defining property of a BST is that in-order traversal yields sorted output, which is invaluable for sorted iteration and range queries. Self-balancing BSTs (AVL, Red-Black, B-tree) maintain O(log n) worst case via rotations. Java's `TreeMap`, `TreeSet`, and treeified HashMap buckets all use Red-Black trees — chosen for fewer rotations than AVL while still providing O(log n) guarantees. In Java, you implement plain binary trees yourself (no built-in), but use `TreeMap`/`TreeSet` for ordered storage, `HashMap`/`HashSet` for unordered O(1) average lookups, `LinkedHashMap` for O(1) lookups with insertion-order iteration, and `PriorityQueue` for min/max access only. Don't roll your own BST in production — it's a classic source of O(n) worst-case bugs; use TreeMap/TreeSet. The mental model: binary tree = hierarchy; BST = ordered hierarchy with O(log n) ops; balanced BST = guaranteed O(log n). Choose Red-Black (TreeMap) for general-purpose ordered storage, AVL for read-heavy workloads, B-tree/B+ tree for disk-resident data (databases), and heap for min/max-only access.