Algorithms and Problem Solving with Java
Trees and Binary Search Tree Fundamentals
আপনি একটি free preview lesson দেখছেন।
Lesson Overview
এ পর্যন্ত আমরা mostly linear data structures দেখেছি।
Examples:
Array
List
Queue
Stack
Deque
এগুলোর data সাধারণত একধরনের sequence হিসেবে ভাবা যায়।
কিন্তু অনেক real-world relationship naturally hierarchical।
Examples:
File system
Organization structure
Course modules and lessons
Category hierarchy
HTML document structure
Decision trees
এই ধরনের structure বোঝার জন্য গুরুত্বপূর্ণ abstraction হলো:
Tree
এই lesson-এ আমরা শিখব:
- What a tree is
- Root
- Parent and child
- Leaf node
- Sibling
- Depth
- Height
- Subtree
- Binary Tree
- Binary Search Tree
- BST ordering property
- Searching a BST
- Inserting into a BST
- In-order traversal
- Pre-order traversal
- Post-order traversal
- Recursive tree processing
- Balanced vs unbalanced trees
- Average and worst-case complexity
- Why production ordered collections use balanced trees
What Is a Tree?
A tree is a hierarchical data structure made of:
nodes
connected through relationships।
Example:
A
/ \
B C
/ \
D E
Here:
A
B
C
D
E
are nodes।
Tree Is Hierarchical
Unlike an array:
A B C D E
a tree represents relationships such as:
A contains B and C
B contains D and E
This gives us levels and branches।
Root
The topmost node is called the:
root
Example:
A
/ \
B C
Root:
A
A tree has one root in the standard rooted-tree model we use here।
Parent and Child
If one node directly connects downward to another:
A
|
B
then:
A → parent
B → child
Example:
A
/ \
B C
A is parent of:
B
C
and B, C are children of A।
Siblings
Nodes with the same parent are called:
siblings
Example:
A
/ \
B C
B and C are siblings।
Leaf Node
A node with no children is called a:
leaf
Example:
A
/ \
B C
/ \
D E
Leaves:
C
D
E
because they have no children।
Internal Node
A node with at least one child is sometimes called an:
internal node
In the example:
A
B
are internal nodes।
Subtree
Every node can be viewed as the root of its own smaller tree।
Example:
A
/ \
B C
/ \
D E
Subtree rooted at B:
B
/ \
D E
This recursive structure is one reason recursion works so naturally with trees।
Depth
Depth describes how far a node is from the root।
If root depth is:
0
then:
A depth 0
/ \
B C depth 1
/ \
D E depth 2
So:
depth(A) = 0
depth(B) = 1
depth(D) = 2
Height
Height describes the longest downward path from a node to a leaf।
For the whole tree, height describes how deep the tree extends।
Different books sometimes use slightly different edge/node counting conventions।
For this course, the exact off-by-one convention is less important than the intuition:
Depth
→ distance from root downward to a node
Height
→ longest distance from a node downward to a leaf
Why Height Matters
Tree operation complexity often depends on:
height
If a tree has small height:
search may be fast
If the tree becomes extremely tall:
search may become slow
This becomes critical with Binary Search Trees।
Binary Tree
A Binary Tree is a tree where each node has at most:
2 children
These are usually called:
left child
right child
Example:
10
/ \
5 20
A Binary Tree Does Not Automatically Have Search Ordering
This is a valid Binary Tree:
10
/ \
50 3
There is no rule saying:
left < root < right
unless we specifically define the tree as a:
Binary Search Tree
Binary Search Tree
A Binary Search Tree, or:
BST
is a Binary Tree with an ordering rule।
For each node:
values in left subtree
<
node value
values in right subtree
>
node value
For this lesson, we will avoid duplicate values to keep the rule simple।
BST Example
40
/ \
20 60
/ \ / \
10 30 50 70
For root 40:
left subtree values
10, 20, 30
<
40
and:
right subtree values
50, 60, 70
>
40
The same rule applies recursively to every subtree।
BST Is Recursively Ordered
Look at subtree:
20
/ \
10 30
Again:
10 < 20 < 30
Subtree:
60
/ \
50 70
Again:
50 < 60 < 70
This recursive ordering makes efficient searching possible।
Basic BST Node
We can represent a node as:
class Node {
private final int value;
private Node left;
private Node right;
Node(
int value
) {
this.value =
value;
}
int value() {
return value;
}
Node left() {
return left;
}
Node right() {
return right;
}
void setLeft(
Node left
) {
this.left =
left;
}
void setRight(
Node right
) {
this.right =
right;
}
}
For learning algorithms, this mutable node is sufficient।
Searching a BST
Suppose tree:
40
/ \
20 60
/ \ / \
10 30 50 70
Search:
50
Start at:
40
Since:
50 > 40
go right।
Now at:
60
Since:
50 < 60
go left।
Now:
50
found।
Why BST Search Can Be Fast
At each node, ordering lets us discard an entire subtree।
If:
target < current
we do not need the right subtree।
If:
target > current
we do not need the left subtree।
This resembles Binary Search conceptually।
Iterative BST Search
static boolean contains(
Node root,
int target
) {
Node current =
root;
while (
current != null
) {
if (
target == current.value()
) {
return true;
}
if (
target < current.value()
) {
current =
current.left();
} else {
current =
current.right();
}
}
return false;
}
Search Trace
Search 30:
Start 40
30 < 40
→ left
At 20
30 > 20
→ right
At 30
found
Only three nodes inspected।
Missing Value
Search:
25
Process:
40
→ left
20
→ right
30
→ left
But:
30.left == null
So target does not exist।
Recursive BST Search
Trees are recursive structures, so recursive search is natural।
static boolean contains(
Node node,
int target
) {
if (
node == null
) {
return false;
}
if (
target == node.value()
) {
return true;
}
if (
target < node.value()
) {
return contains(
node.left(),
target
);
}
return contains(
node.right(),
target
);
}
Recursive Structure
Notice:
Search current node
↓
If needed,
search one subtree
A subtree is itself a tree।
That is why recursion maps naturally to BST operations।
Inserting into a BST
Suppose tree:
40
/ \
20 60
Insert:
30
Start at 40:
30 < 40
→ go left
At 20:
30 > 20
→ go right
Right is empty।
Insert:
30
Result:
40
/ \
20 60
\
30
Recursive Insert
One clean implementation returns the root of the updated subtree।
static Node insert(
Node node,
int value
) {
if (
node == null
) {
return new Node(
value
);
}
if (
value < node.value()
) {
node.setLeft(
insert(
node.left(),
value
)
);
} else if (
value > node.value()
) {
node.setRight(
insert(
node.right(),
value
)
);
}
return node;
}
Why Return Node?
Suppose:
node.left()
is null।
Recursive call:
insert(
null,
value
)
creates:
new Node(value)
That returned node must become:
node.left
or:
node.right
Returning the updated subtree root makes this pattern elegant।
Duplicate Values
Our implementation does:
if (
value < node.value()
) {
...
} else if (
value > node.value()
) {
...
}
If values are equal:
do nothing
So duplicates are ignored।
BST Duplicate Policy
Real BST designs need an explicit duplicate policy।
Possible approaches:
Reject duplicates
Store count
Always place equal values on one side
Store multiple associated values
There is no universal answer।
For this lesson:
No duplicate nodes
keeps the ordering simple।
Building a BST
Node root =
null;
root =
insert(
root,
40
);
root =
insert(
root,
20
);
root =
insert(
root,
60
);
root =
insert(
root,
10
);
root =
insert(
root,
30
);
root =
insert(
root,
50
);
root =
insert(
root,
70
);
Result:
40
/ \
20 60
/ \ / \
10 30 50 70
Tree Traversal
Sometimes we do not want to search for only one value।
We want to visit:
every node
The order in which we visit them is called:
traversal
Three fundamental depth-first traversal orders are:
In-order
Pre-order
Post-order
In-Order Traversal
Order:
Left
Node
Right
Mnemonic:
L N R
Implementation:
static void inOrder(
Node node
) {
if (
node == null
) {
return;
}
inOrder(
node.left()
);
System.out.println(
node.value()
);
inOrder(
node.right()
);
}
In-Order on a BST
Given:
40
/ \
20 60
/ \ / \
10 30 50 70
In-order produces:
10
20
30
40
50
60
70
This is sorted ascending order।
Why In-Order Produces Sorted Values
BST guarantees:
left values < node < right values
In-order visits:
left
then node
then right
So values emerge in sorted order।
This is one of the most important BST properties।
Pre-Order Traversal
Order:
Node
Left
Right
Mnemonic:
N L R
Implementation:
static void preOrder(
Node node
) {
if (
node == null
) {
return;
}
System.out.println(
node.value()
);
preOrder(
node.left()
);
preOrder(
node.right()
);
}
Pre-Order Example
For:
40
/ \
20 60
/ \ / \
10 30 50 70
Result:
40
20
10
30
60
50
70
Root is visited before its subtrees।
Post-Order Traversal
Order:
Left
Right
Node
Mnemonic:
L R N
Implementation:
static void postOrder(
Node node
) {
if (
node == null
) {
return;
}
postOrder(
node.left()
);
postOrder(
node.right()
);
System.out.println(
node.value()
);
}
Post-Order Example
Result:
10
30
20
50
70
60
40
Children are processed before the parent।
Why Different Traversals Exist
Different algorithms need different processing orders।
In-order:
BST values in sorted order
Pre-order:
Parent before descendants
Post-order:
Children before parent
Example Use Cases
Conceptually:
In-order
Produce BST values in sorted order
Pre-order
Serialize/copy hierarchy where parent comes first
Post-order
Delete/free child structures before parent
Calculate values that depend on children
Traversal Complexity
Each traversal visits every node once।
For:
n nodes
time:
O(n)
Traversal Space
Recursive traversal uses the call stack।
Space depends on tree height:
O(h)
where:
h = tree height
Balanced tree:
h ≈ log n
Highly unbalanced tree:
h ≈ n
Balanced BST
Consider:
40
/ \
20 60
/ \ / \
10 30 50 70
This tree is reasonably balanced।
Left and right subtree sizes are not dramatically different।
Height is small relative to node count।
Search in a Balanced BST
At each step, a substantial portion of the remaining tree is excluded।
For a well-balanced BST:
Search
Insert
can be approximately:
O(log n)
Unbalanced BST
Now insert values in this order:
10
20
30
40
50
A simple BST becomes:
10
\
20
\
30
\
40
\
50
This looks almost like a linked list।
Search in an Unbalanced BST
Search:
50
requires:
10
20
30
40
50
Every node may need to be visited।
Worst case:
O(n)
BST Does Not Guarantee O(log n)
This is critical।
A plain Binary Search Tree has:
average-ish O(log n)
only when its shape stays reasonably balanced।
Worst case:
O(n)
Why Binary Search Is Different
Binary Search on an array always chooses the middle index:
half
half
half
A plain BST's shape depends on insertion order।
If insertion order is poor:
tree can become skewed
So plain BST search does not automatically guarantee logarithmic behavior।
Self-Balancing Trees
Production ordered tree structures often use more sophisticated trees that automatically maintain balance।
Examples include:
AVL Tree
Red-Black Tree
We will not implement those in this foundation course।
The important idea:
Balance protects tree height.
Java TreeMap and TreeSet
Java provides ordered collections:
TreeMap
TreeSet
These use a self-balancing tree strategy internally rather than a naive BST।
This gives operations such as:
get
put
contains
remove
with logarithmic-style guarantees:
O(log n)
for the relevant operations।
Why Not Use Our BST in Production?
Our implementation teaches:
BST ordering
search
insert
traversal
complexity
But it does not implement:
balancing
deletion
iterators
concurrency behavior
full collection contracts
edge-case handling
For normal Java applications, use standard collections unless a custom tree is specifically required।
BST vs HashMap
Suppose we need lookup by key।
HashMap:
Average exact lookup
→ O(1)
Sorted order
→ No
TreeMap:
Lookup
→ O(log n)
Sorted keys
→ Yes
So:
HashMap
is often better for exact lookup।
TreeMap
is useful when ordering matters।
BST vs Binary Search
Both rely on ordered data।
Binary Search:
Usually array/list based
Requires sorted sequence
O(log n) lookup
Insertion into array may be O(n)
Balanced BST:
Tree based
Maintains ordering dynamically
Search O(log n)
Insert O(log n)
This is why trees are useful for dynamic ordered data।
BST vs Heap
Do not confuse them।
BST
Rule:
left < node < right
Useful for:
search
ordered traversal
range-style operations
Heap
Rule:
parent <= children
or:
parent >= children
Useful for:
minimum/maximum priority
Heap cannot efficiently perform arbitrary ordered search like a BST।
BST vs HashSet
Suppose only need:
Does value exist?
A HashSet may provide expected:
O(1)
membership।
A tree-based set may provide:
O(log n)
but also sorted order।
Again:
access pattern determines structure.
Minimum Value in a BST
In a BST:
minimum
is the leftmost node।
Example:
40
/ \
20 60
/
10
Minimum:
10
Find Minimum
static int min(
Node root
) {
if (
root == null
) {
throw new IllegalArgumentException(
"Tree is empty."
);
}
Node current =
root;
while (
current.left()
!= null
) {
current =
current.left();
}
return current.value();
}
Maximum Value
Maximum is the rightmost node।
static int max(
Node root
) {
if (
root == null
) {
throw new IllegalArgumentException(
"Tree is empty."
);
}
Node current =
root;
while (
current.right()
!= null
) {
current =
current.right();
}
return current.value();
}
Complexity of Min/Max
Depends on height:
O(h)
Balanced:
O(log n)
Worst skewed:
O(n)
Counting Nodes
A recursive tree problem:
static int size(
Node node
) {
if (
node == null
) {
return 0;
}
return 1
+ size(
node.left()
)
+ size(
node.right()
);
}
Why This Works
For every node:
1
+
size of left subtree
+
size of right subtree
A tree is naturally defined in terms of smaller trees।
Size Complexity
Every node is visited once।
Time:
O(n)
Recursive stack:
O(h)
Computing Tree Height
One possible convention:
static int height(
Node node
) {
if (
node == null
) {
return -1;
}
int leftHeight =
height(
node.left()
);
int rightHeight =
height(
node.right()
);
return 1
+ Math.max(
leftHeight,
rightHeight
);
}
With this convention:
empty tree height = -1
leaf height = 0
Other conventions may use different base values।
Be consistent within one codebase।
Height Uses Post-Order Reasoning
To calculate a node's height, we first need:
left subtree height
right subtree height
Then:
1 + maximum
So children must be solved before parent।
This is post-order style thinking।
Tree Algorithms Often Follow Structural Meaning
Ask:
Do I need the parent before children?
→ Pre-order-like
Do I need sorted BST order?
→ In-order
Do I need child results before parent?
→ Post-order-like
This is more useful than memorizing traversal names alone।
Iterative In-Order Traversal
Recursion is not the only option।
We can use an explicit Stack:
static void inOrderIterative(
Node root
) {
Deque<Node> stack =
new ArrayDeque<>();
Node current =
root;
while (
current != null
|| !stack.isEmpty()
) {
while (
current != null
) {
stack.push(
current
);
current =
current.left();
}
current =
stack.pop();
System.out.println(
current.value()
);
current =
current.right();
}
}
Why Stack Works
In-order requires:
Go left as far as possible
Then return to parent
Then go right
The Stack remembers the chain of parents we need to return to।
Recursive vs Iterative Tree Traversal
Recursive:
Short
Natural
Easy to read
But deep trees can cause:
StackOverflowError
Iterative:
Explicit state
More code
More control
For balanced trees, recursion depth may be manageable।
For arbitrary untrusted depth, explicit stacks can be safer।
Common Mistake 1 — Binary Tree Means BST
False।
A Binary Tree only limits child count।
A BST adds an ordering property।
Common Mistake 2 — Comparing Only Immediate Children
BST property applies to:
entire subtrees
not just immediate children।
This is invalid:
20
/ \
10 30
/
5
Although:
5 < 30
it is in the right subtree of 20, where all values should be:
> 20
So the BST rule is violated।
Common Mistake 3 — Calling Plain BST Always O(log n)
Wrong।
If unbalanced:
O(n)
is possible।
Common Mistake 4 — Forgetting Null Base Case
Recursive tree algorithms usually need:
if (
node == null
) {
...
}
Without a proper base case, recursion fails।
Common Mistake 5 — Wrong In-Order Order
In-order is:
Left
Node
Right
not:
Node
Left
Right
The latter is Pre-order।
Common Mistake 6 — Assuming Heap and BST Are the Same
Heap only guarantees parent-child priority।
BST provides full subtree ordering relative to each node।
They optimize different operations।
Common Mistake 7 — Ignoring Duplicate Policy
If duplicates can occur, define exactly what should happen।
Do not let duplicate behavior happen accidentally।
Common Mistake 8 — Insertion Order Does Not Matter
For a plain BST, insertion order can dramatically affect tree shape and performance।
Common Mistake 9 — Writing Custom BST for Standard Map Needs
If you need an ordered map:
TreeMap
already exists।
Use custom trees for learning or genuinely specialized requirements।
Common Mistake 10 — Recursive Depth Is Always Safe
A highly skewed tree may create:
O(n)
recursive depth and potentially overflow the call stack।
Practical Example — Complete BST
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
public static void main(String[] args) {
Node root =
null;
int[] values = {
40,
20,
60,
10,
30,
50,
70
};
for (
int value
: values
) {
root =
insert(
root,
value
);
}
System.out.println(
"Contains 50: "
+ contains(
root,
50
)
);
System.out.println(
"Contains 25: "
+ contains(
root,
25
)
);
System.out.println(
"Min: "
+ min(
root
)
);
System.out.println(
"Max: "
+ max(
root
)
);
System.out.println(
"Size: "
+ size(
root
)
);
System.out.println(
"In-order:"
);
inOrder(
root
);
System.out.println(
"Pre-order:"
);
preOrder(
root
);
System.out.println(
"Post-order:"
);
postOrder(
root
);
}
static Node insert(
Node node,
int value
) {
if (
node == null
) {
return new Node(
value
);
}
if (
value < node.value()
) {
node.setLeft(
insert(
node.left(),
value
)
);
} else if (
value > node.value()
) {
node.setRight(
insert(
node.right(),
value
)
);
}
return node;
}
static boolean contains(
Node root,
int target
) {
Node current =
root;
while (
current != null
) {
if (
target == current.value()
) {
return true;
}
if (
target < current.value()
) {
current =
current.left();
} else {
current =
current.right();
}
}
return false;
}
static int min(
Node root
) {
if (
root == null
) {
throw new IllegalArgumentException(
"Tree is empty."
);
}
Node current =
root;
while (
current.left()
!= null
) {
current =
current.left();
}
return current.value();
}
static int max(
Node root
) {
if (
root == null
) {
throw new IllegalArgumentException(
"Tree is empty."
);
}
Node current =
root;
while (
current.right()
!= null
) {
current =
current.right();
}
return current.value();
}
static int size(
Node node
) {
if (
node == null
) {
return 0;
}
return 1
+ size(
node.left()
)
+ size(
node.right()
);
}
static void inOrder(
Node node
) {
if (
node == null
) {
return;
}
inOrder(
node.left()
);
System.out.println(
node.value()
);
inOrder(
node.right()
);
}
static void preOrder(
Node node
) {
if (
node == null
) {
return;
}
System.out.println(
node.value()
);
preOrder(
node.left()
);
preOrder(
node.right()
);
}
static void postOrder(
Node node
) {
if (
node == null
) {
return;
}
postOrder(
node.left()
);
postOrder(
node.right()
);
System.out.println(
node.value()
);
}
static final class Node {
private final int value;
private Node left;
private Node right;
Node(
int value
) {
this.value =
value;
}
int value() {
return value;
}
Node left() {
return left;
}
Node right() {
return right;
}
void setLeft(
Node left
) {
this.left =
left;
}
void setRight(
Node right
) {
this.right =
right;
}
}
}
Practice 1 — Identify Tree Terms
Given:
A
/ \
B C
/ \
D E
Answer:
Root?
Children of C?
Leaves?
Sibling of D?
Answer
Root:
A
Children of C:
D, E
Leaves:
B, D, E
Sibling of D:
E
Practice 2 — Is It a Binary Tree?
A
/ | \
B C D
Answer
No।
A has three children।
A Binary Tree permits at most two children per node।
Practice 3 — Is It a BST?
20
/ \
10 30
Answer
Yes।
Practice 4 — Is It a BST?
20
/ \
10 30
/
15
Answer
No।
15 is in the right subtree of 20, but:
15 < 20
The entire right subtree must contain values greater than 20।
Practice 5 — Search Path
Tree:
40
/ \
20 60
/ \ / \
10 30 50 70
Search:
70
Answer
40
→ 60
→ 70
Practice 6 — Search Missing Value
Search:
25
Answer
40
→ 20
→ 30
→ left null
Not found।
Practice 7 — In-Order
For:
20
/ \
10 30
what is In-order traversal?
Answer
10
20
30
Practice 8 — Pre-Order
Answer
20
10
30
Practice 9 — Post-Order
Answer
10
30
20
Practice 10 — Insert
Insert:
25
into:
20
/ \
10 30
Answer
20
/ \
10 30
/
25
Practice 11 — Complexity
Balanced BST search:
?
Answer
Approximately:
O(log n)
Practice 12 — Worst Case
Plain unbalanced BST search:
?
Answer
O(n)
Practice 13 — TreeMap or HashMap?
Need:
Fast exact lookup
No ordering requirement
Answer
Usually:
HashMap
Practice 14 — TreeMap or HashMap?
Need:
Keys in sorted order
Answer
Usually:
TreeMap
Practice 15 — Heap or BST?
Need:
Repeatedly remove smallest item
Answer
A:
Min Heap / PriorityQueue
is often the more direct abstraction।
True or False
- Every Tree is a Binary Tree.
- Every Binary Tree is a Binary Search Tree.
- A BST has an ordering rule.
- BST left-subtree values are smaller than the node.
- BST right-subtree values are larger than the node in our simplified model.
- In-order traversal of a BST produces sorted values.
- Pre-order visits the node before its children.
- Post-order visits the node after its subtrees.
- Plain BST lookup is always
O(log n). - A skewed BST can behave like a linked list.
- Tree height affects operation complexity.
TreeMapuses a more sophisticated balanced tree rather than a naive BST.- A Heap and BST provide the same ordering guarantees.
- Recursive tree traversal uses call-stack space.
Answers
1. False
2. False
3. True
4. True
5. True
6. True
7. True
8. True
9. False
10. True
11. True
12. True
13. False
14. True
Knowledge Check
Question 1
What is a root node?
Question 2
What is a leaf?
Question 3
What is a subtree?
Question 4
What makes a Binary Tree different from a general tree?
Question 5
What additional rule makes a Binary Tree a Binary Search Tree?
Question 6
Why can BST search avoid exploring one whole subtree?
Question 7
What is In-order traversal order?
Question 8
Why does In-order traversal produce sorted values for a BST?
Question 9
What is Pre-order traversal?
Question 10
What is Post-order traversal?
Question 11
Why can a plain BST degrade to O(n) search?
Question 12
Why do production ordered collections use self-balancing trees?
Knowledge Check Answers
Answer 1
The root is the topmost node of a rooted tree and has no parent inside that tree।
Answer 2
A leaf is a node with no children।
Answer 3
A subtree is a node together with all descendants beneath it, viewed as a smaller tree।
Answer 4
A Binary Tree allows at most two children per node, usually identified as left and right।
Answer 5
For each node, values in the left subtree must be ordered below the node and values in the right subtree above the node according to the tree's comparison rule।
Answer 6
Because ordering tells us that if the target is smaller than the current node, it cannot exist in the right subtree, and vice versa।
Answer 7
Left
Node
Right
Answer 8
Because BST ordering guarantees that every left-subtree value comes before the node and every right-subtree value comes after it।
Answer 9
Node
Left
Right
The parent is processed before its descendants।
Answer 10
Left
Right
Node
The children/subtrees are processed before the parent।
Answer 11
Insertion order can create a highly skewed tree where each node has effectively only one child, giving tree height close to n।
Answer 12
Balancing keeps tree height near logarithmic so search, insertion, and removal can maintain predictable O(log n) behavior rather than degrading toward linear time।
Practical Decision Guide
Use:
HashMap
when:
Exact key lookup is the priority
and sorted order is unnecessary.
Use:
TreeMap
when:
Keys must remain ordered
or ordered navigation matters.
Use:
PriorityQueue
when:
Repeated access to minimum/maximum priority
is the main operation.
Use:
Binary Search
when:
You already have a sorted indexed sequence.
Use a custom BST mainly when:
Learning tree algorithms
or solving a specialized tree-specific problem.
Complexity Summary
For a plain BST:
Search:
O(h)
Insert:
O(h)
Min / Max:
O(h)
where:
h = tree height
If reasonably balanced:
h ≈ log n
so:
Search:
O(log n)
Insert:
O(log n)
Worst skewed case:
h ≈ n
so:
Search:
O(n)
Insert:
O(n)
Traversing all nodes:
O(n)
Core Mental Model
A Binary Search Tree asks:
Is the target smaller or larger
than the current node?
Then it chooses one direction:
smaller
→ left
larger
→ right
Its performance depends heavily on:
tree height
Therefore:
Balanced tree
→ fast logarithmic-style navigation
Skewed tree
→ linear-style navigation
Lesson Summary
এই lesson-এ আমরা Trees এবং Binary Search Trees-এর foundation শিখেছি।
We learned:
- Trees represent hierarchical relationships
- A tree contains nodes connected through parent-child relationships
- Root is the topmost node
- Leaves have no children
- A subtree is itself a smaller tree
- Depth measures distance from the root
- Height describes downward tree depth
- Binary Trees allow at most two children per node
- Binary Search Trees add an ordering rule
- BST search follows only one relevant branch
- BST insertion preserves ordering recursively
- Duplicate values require an explicit policy
- In-order traversal is
Left → Node → Right - In-order traversal of a BST produces sorted order
- Pre-order is
Node → Left → Right - Post-order is
Left → Right → Node - Tree traversals generally take
O(n)time - Recursive traversal uses
O(h)call-stack space - Balanced BST operations can approach
O(log n) - Unbalanced BST operations can degrade to
O(n) - Insertion order affects a plain BST's shape
- Production ordered collections use self-balancing trees
TreeMapandTreeSetprovide ordered tree-based collection behavior- BST, Heap, HashMap, and Binary Search optimize different access patterns
The central BST rule is:
Left subtree
<
Node
<
Right subtree
And the most important performance idea is:
BST performance is really about height.
Small height
→ efficient navigation
Large height
→ slow navigation
Next Lesson
পরবর্তী lesson:
Module Practice and Assessment
আমরা Module 6-এর সব নতুন concepts একসঙ্গে apply করব:
- Big-O reasoning
- Linear Search
- Binary Search
- Sorting
- Merge Sort and Quick Sort
- Java sorting/searching APIs
- Stack and Queue algorithms
- Heap and
PriorityQueue - Hashing
HashMapHashSet- Binary Search Trees
- Traversals
- Choosing the correct data structure and algorithm