---
title: "FP-tree and conditional FP-tree"
subject: "Data Mining"
chapter: 4
key: "semester_7/data_mining:fp-tree-conditional"
source: https://www.bctengineer.com/q/semester_7/data_mining/fp-tree-conditional
site: BCT Engineering
---

# FP-tree and conditional FP-tree

Data Mining · Chapter 4: Association Analysis

- Asked in: year not given
- Video: [1. Frequent Pattern (FP) Growth Algorithm Association Rule Mining Solved Example by Mahesh Huddar](https://www.youtube.com/watch?v=7oGz4PCp9jI) — Mahesh Huddar
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/data_mining/fp-tree-conditional
- Whole chapter: https://www.bctengineer.com/md/semester_7/data_mining/chapter-4

## Question

What are FP-Tree and Conditional FP-Tree? Explain with example.

## Short answer

FP-tree is a prefix tree storing frequent items sorted by support, with node counts and header table links. Conditional pattern base for item i is prefix paths ending before i. Conditional FP-tree built from this base (keeping items ≥ min_sup) is mined recursively to find patterns ending with i. Example shows mining A and E.

## Answer

#### FP-tree
An **FP-tree (Frequent Pattern tree)** is a compact prefix-tree representation of a transaction database, used by the FP-growth algorithm.

- It has a **root** labelled "null". Every other node stores an item name, a **count** (number of transactions passing through the node) and a link to the parent and to the next node with the same item.
- Frequent items in each transaction are sorted by descending support, and the transaction is inserted as a path. Common prefixes are shared, so the tree is usually much smaller than the database.
- A **header table** lists the frequent items with their counts and a pointer to the first node of each item (node-links).

#### Conditional pattern base and conditional FP-tree
- The **conditional pattern base** of an item *i* is the set of prefix paths in the FP-tree that end just before the nodes of *i*, each with the count of the node of *i*.
- The **conditional FP-tree** of *i* is the FP-tree built from this pattern base, keeping only items whose total count ≥ min_sup. It is used to find the frequent patterns that end with *i*, and is mined recursively.

#### Example
Transactions (min_sup = 2): T1 {A, C, D}, T2 {B, C, E}, T3 {A, B, C, E}, T4 {B, E}, T5 {A, B, C, E}.

Frequent items sorted: B:4, C:4, E:4, A:3 (D is dropped). The FP-tree:

```text
null
 |-- C:1 -- A:1
 |-- B:4
      |-- C:3 -- E:3 -- A:2
      |-- E:1
```
Header table: B → C → E → A with node-links.

For item **A** (A:2 under E, A:1 under C):
- Conditional pattern base: {B, C, E : 2}, {C : 1}.
- Conditional FP-tree (min_sup = 2): items B:2, C:3, E:2.
```text
null
 |-- C:1
 |-- B:2 -- C:2 -- E:2
```
- Mining it gives patterns {A, C}:3, {A, B}:2, {A, E}:2, {A, B, C}:2, {A, B, E}:2, {A, C, E}:2, {A, B, C, E}:2.

For item **E**: pattern base {B, C : 3}, {B : 1}; conditional FP-tree has B:4, C:3 → {E, B}:4, {E, C}:3, {E, B, C}:3.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does each non-root node of an FP-tree store?
   A. Item name, count, and links to parent and next node of same item
   B. Only the item name
   C. A transaction ID and its support
   D. The confidence of its rule
   Answer: A. Counts record how many transactions pass through the node; node-links join same-item nodes. (Key point: FP-tree structure)

2. Why is the FP-tree usually much smaller than the database?
   A. Infrequent and frequent items are both merged
   B. Transactions sorted by descending support share common prefixes
   C. Each transaction is stored only once without counts
   D. It stores only the 1-itemsets
   Answer: B. Shared prefixes increase node counts instead of adding nodes. (Key point: Prefix sharing)

3. What is the conditional pattern base of item i?
   A. All transactions containing i
   B. The sub-tree below nodes of i
   C. The prefix paths ending just before nodes of i, each with the count of i's node
   D. The frequent items with the highest count
   Answer: C. It collects prefix paths that lead to i. (Key point: Pattern base)

4. For item A, pattern base {B,C,E:2}, {C:1} and min_sup 2: which items stay in the conditional FP-tree?
   A. B:1, C:1, E:1
   B. Only C:3
   C. B:2 and E:2 only
   D. B:2, C:3, E:2
   Answer: D. Item counts are summed over paths: B 2, C 2+1 = 3, E 2, all >= 2. (Key point: Conditional FP-tree)

## Related in Data Mining

- [FP-tree on HotDogs data](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Afp-tree-hotdogs) — Data Mining, chapter 4
- [FP-tree on t1-t5 data](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Afp-tree-t1-t5) — Data Mining, chapter 4
- [ID3 steps, overfitting, TP/FP/recall](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aid3-steps-overfitting-recall) — Data Mining, chapter 3