The Central Idea
A decision tree organizes a multi-stage counting problem by drawing the available choices at each stage as branches.
The starting point is called the root. Each branch represents a possible choice, and each endpoint represents a completed sequence of choices.
The number of complete root-to-endpoint paths equals the number of complete outcomes.
A Simple Two-Stage Tree
Suppose a meal consists of one entrée and one beverage.
There are \(3\) entrées:
\[ E_1,\qquad E_2,\qquad E_3 \]and \(2\) beverages:
\[ B_1,\qquad B_2. \]From each entrée branch, the tree splits into two beverage branches.
The completed paths are
\[ (E_1,B_1),\ (E_1,B_2),\ (E_2,B_1),\ (E_2,B_2),\ (E_3,B_1),\ (E_3,B_2). \]Therefore,
\[ \boxed{6} \]complete outcomes are possible.
Decision Trees Visualize the Product Principle
In the previous example, every one of the \(3\) first-stage branches has \(2\) second-stage continuations.
Therefore, the tree contains
\[ 3\cdot2=6 \]complete paths.
A regular decision tree is a visual form of the product principle.
Text Representation of a Tree
A decision tree does not require a graphical drawing to be useful. Its branching structure can also be shown in text.
Start
├── E1
│ ├── B1
│ └── B2
├── E2
│ ├── B1
│ └── B2
└── E3
├── B1
└── B2
Each path from Start to a beverage is one complete meal.
Reading a Decision Tree
When reading a decision tree:
- begin at the root;
- choose one branch at the first stage;
- continue through one branch at each later stage;
- stop when a complete outcome has been formed.
Every full path is counted once.
Three-Stage Trees
Suppose an outfit requires:
- one of \(2\) shirts;
- one of \(3\) pairs of pants;
- one of \(2\) pairs of shoes.
Each shirt branch splits into \(3\) pants branches, and each shirt-pants branch splits into \(2\) shoe branches.
The total number of leaves is
\[ 2\cdot3\cdot2=12. \]Thus,
\[ \boxed{12} \]complete outfits are possible.
Leaves Represent Complete Outcomes
The endpoints of a decision tree are often called leaves.
In a counting tree, a leaf normally represents one completed sequence of decisions.
Counting the leaves is therefore equivalent to counting the complete outcomes, provided each valid outcome appears exactly once.
Unequal Branches
Decision trees become especially valuable when different branches have different numbers of continuations.
Suppose a traveler may choose route \(A\), \(B\), or \(C\) at the first stage.
- Route \(A\) has \(2\) possible continuations.
- Route \(B\) has \(4\) possible continuations.
- Route \(C\) has \(3\) possible continuations.
The tree has
\[ 2+4+3=9 \]leaves.
Therefore,
\[ \boxed{9} \]complete trips are possible.
Why One Product Does Not Always Work
In the unequal-branch example, the first stage has \(3\) choices, but there is no single number of second-stage choices shared by all three branches.
Therefore, neither
\[ 3\cdot2,\qquad 3\cdot3,\qquad \text{nor}\qquad 3\cdot4 \]gives the correct total.
Instead, count the leaves of each branch and add:
\[ \boxed{2+4+3=9}. \]Branches as Cases
Each first-stage branch can be treated as a separate case.
Within a branch, the product principle may count the later stages.
Across disjoint first-stage branches, the resulting totals are added.
Decision trees therefore provide a natural bridge between the product principle and counting by cases.
Example: Different Meal Rules
A restaurant offers three entrées:
- Entrée \(A\) may be paired with \(4\) sides.
- Entrée \(B\) may be paired with \(3\) sides.
- Entrée \(C\) may be paired with \(5\) sides.
A tree begins with three entrée branches.
Their leaf counts are
\[ 4,\qquad3,\qquad5. \]The total number of meals is
\[ \boxed{4+3+5=12}. \]Restrictions Appear as Missing Branches
A restriction can often be represented by simply omitting an invalid branch.
Suppose a two-letter string is formed from
\[ \{A,B,C\} \]without repetition.
After choosing \(A\) first, only \(B\) and \(C\) remain. The branch from \(A\) back to \(A\) does not appear.
The same logic applies after choosing \(B\) or \(C\).
Example: No Repetition
Form a two-letter string from
\[ \{A,B,C,D\} \]without repetition.
The first stage has \(4\) branches.
From each first-stage branch, only \(3\) letters remain.
Therefore,
\[ \boxed{4\cdot3=12}. \]Repeated Choices Produce Repeated Branch Labels
If repetition is allowed, the same label may appear on several stages.
For example, a two-digit code using \(0,1,2\) with repetition allowed has \(3\) branches at the first stage and \(3\) branches from each of those nodes.
The total is
\[ \boxed{3\cdot3=9}. \]Decision Trees and Conditional Rules
Some rules depend on what was chosen earlier.
Suppose a customer chooses either a basic or premium package.
- A basic package offers \(2\) add-ons.
- A premium package offers \(5\) add-ons.
The number of second-stage choices depends on the first-stage decision.
A decision tree displays this dependency immediately.
Example: Conditional Product Choices
A computer system has two base models.
- Model \(A\) supports \(3\) processors and \(2\) memory options.
- Model \(B\) supports \(2\) processors and \(4\) memory options.
For model \(A\):
\[ 3\cdot2=6. \]For model \(B\):
\[ 2\cdot4=8. \]Add the disjoint model cases:
\[ \boxed{6+8=14}. \]A Tree Can Encode Probability and Counting
The same branching structure used for counting can later be used for probability.
In counting, branches record possible choices and leaves record outcomes.
In probability, branches may also be labeled with probabilities.
For now, the tree is being used only to determine how many distinct outcomes are possible.
Example: Coin Tosses
A coin toss has two possible outcomes:
\[ H\qquad\text{or}\qquad T. \]For two tosses, each first-toss branch splits into two second-toss branches.
The leaves are
\[ HH,\qquad HT,\qquad TH,\qquad TT. \]Thus,
\[ \boxed{4} \]outcome sequences are possible.
Three Coin Tosses
A third toss adds another two-way split after every second-toss outcome.
Therefore,
\[ 2\cdot2\cdot2=2^3=8. \]The tree has
\[ \boxed{8} \]leaves.
Binary Trees
A tree in which every nonterminal node has two branches is called a binary tree.
A full binary decision process with \(n\) stages has
\[ \boxed{2^n} \]root-to-leaf paths.
Binary strings, yes-or-no decisions, and repeated coin tosses all have this structure.
Decision Trees and Codes
Suppose a code contains one letter from
\[ \{A,B,C\} \]followed by one digit from
\[ \{1,2,3,4\}. \]The root first splits into \(3\) letter branches.
Each letter branch then splits into \(4\) digit branches.
The tree therefore has
\[ \boxed{3\cdot4=12} \]leaves.
Decision Trees and Functions
A function from
\[ \{a,b\} \]to
\[ \{1,2,3\} \]can be specified by first choosing the image of \(a\), then choosing the image of \(b\).
Each stage has \(3\) branches.
Therefore, there are
\[ \boxed{3^2=9} \]possible functions.
Decision Trees and State Transitions
Decision trees can also represent how a system changes from one state to another.
A node represents the current state, while outgoing branches represent the possible next states.
A complete path then represents one possible evolution of the system through several steps.
Some Branches May End Early
Not every path must contain the same number of stages.
A choice may terminate the process immediately, while another choice may lead to additional decisions.
Decision trees handle this naturally because completed outcomes can occur at different depths.
Example: Early Termination
A customer may choose:
- a standard ticket, which completes the purchase immediately; or
- a premium ticket, followed by one of \(3\) seating upgrades.
The standard branch contributes
\[ 1 \]complete outcome.
The premium branch contributes
\[ 3 \]complete outcomes.
Therefore,
\[ \boxed{1+3=4}. \]Paths Must Represent Distinct Outcomes
A valid counting tree should be constructed so that two different root-to-leaf paths do not represent the same final outcome.
If two paths describe the same outcome, counting leaves will overcount.
The tree should therefore encode a one-to-one correspondence between leaves and outcomes.
Every Valid Outcome Must Appear
A tree can also undercount if a valid branch is accidentally omitted.
After constructing a tree, verify that every allowed choice has been included at each relevant node.
Tree Depth
The depth of a node describes how many branch steps separate it from the root.
In a uniform \(k\)-stage decision process, completed outcomes typically appear at depth \(k\).
When early termination is possible, leaves may occur at different depths.
Counting Leaves Recursively
The number of leaves below a node can be found by adding the leaf counts below its immediate branches.
If a node has branches leading to subtrees containing
\[ L_1,L_2,\ldots,L_k \]leaves, then the node has
\[ \boxed{L_1+L_2+\cdots+L_k} \]descendant leaves.
This viewpoint anticipates recursive counting.
Compressing a Regular Tree
Large trees can become impractical to draw.
If every node at a stage has the same number of branches, we can replace the full drawing with stage counts.
For example, a \(5\)-stage binary tree has
\[ 2^5=32 \]leaves.
There is usually no need to draw all \(32\) endpoints.
When a Tree Is Most Useful
Decision trees are particularly useful when:
- the process has several stages;
- later choices depend on earlier choices;
- different branches have different numbers of continuations;
- some branches terminate early;
- restrictions remove certain choices;
- the structure is easier to see visually than symbolically.
When a Tree Is Not Necessary
A tree may be unnecessary when the structure is completely regular.
If there are \(8\) independent stages with \(10\) choices at every stage, writing
\[ 10^8 \]is more efficient than drawing a tree with one hundred million leaves.
From Trees to Formulas
Decision trees help reveal the arithmetic structure of a problem.
Regular branching suggests multiplication.
Unequal branches suggest addition across cases.
Repeated subtrees often suggest a reusable pattern or recursive formula.
Common Error: Counting Internal Nodes
Internal nodes usually represent partial decisions, not complete outcomes.
Unless the problem specifically treats a partial path as a completed outcome, count the leaves rather than all nodes in the tree.
Common Error: Including Invalid Branches
If repetition is forbidden, branches that reuse an earlier choice must be removed.
Leaving them in the tree causes overcounting.
Common Error: Omitting Valid Branches
Every legal continuation must appear at the appropriate node.
Missing even one branch can remove several complete outcomes if that branch would have led to further stages.
Common Error: Multiplying When Branch Sizes Differ
If first-stage branches have different numbers of continuations, a single product may not work.
Count each branch or subtree separately, then add the totals.
Common Error: Double-Counting the Same Outcome
A well-designed tree should give each complete outcome one unique path.
If the same outcome can be reached through multiple paths, the representation must be revised or the duplicate counts must be corrected.
A Reliable Procedure
- Define what counts as one complete outcome.
- Identify the first decision or stage.
- Draw one branch for each valid first-stage choice.
- From each resulting node, draw every valid next-stage choice.
- Continue until each path represents a complete outcome.
- Remove branches forbidden by restrictions.
- Count the leaves or count the leaves within each subtree.
- Use multiplication for regular repeated branching.
- Use addition to combine disjoint branch totals.
- Verify that each valid outcome appears exactly once.
Example: Full Tree Workflow
A customer chooses either a basic plan or a premium plan.
A basic plan includes one of \(2\) storage options and one of \(3\) support levels.
A premium plan includes one of \(4\) storage options and one of \(2\) support levels.
Basic-plan leaves:
\[ 2\cdot3=6. \]Premium-plan leaves:
\[ 4\cdot2=8. \]The first-stage plan branches are disjoint, so
\[ \boxed{6+8=14}. \]There are \(14\) complete configurations.
Practice 1: Regular Tree
A two-stage process has \(4\) choices at the first stage and \(3\) choices at the second stage after every first-stage choice. How many leaves does the tree have?
Practice 2: Three Stages
A process has \(2\), then \(5\), then \(3\) choices at successive stages. How many complete paths are possible?
Practice 3: Unequal Branches
A first-stage tree has three branches whose subtrees contain \(4\), \(7\), and \(2\) leaves. How many complete outcomes are represented?
Practice 4: No Repetition
A two-letter string is formed from \(6\) distinct letters without repetition. How many leaves would the complete decision tree have?
Practice 5: Coin Toss Tree
How many leaves are in the decision tree for four coin tosses?
Practice 6: Early Termination
A first-stage process has two branches. One branch immediately completes an outcome. The other branch splits into \(5\) completed outcomes. How many leaves are there?
Practice 7: Conditional Choices
Package \(A\) has \(3\) color choices and \(2\) size choices. Package \(B\) has \(5\) color choices and \(4\) size choices. How many complete package configurations are possible?
Practice 8: Binary Tree
A full binary decision tree has \(7\) stages. How many leaves does it have?
Practice 9: Functions as Paths
A function from a three-element set to a four-element set is built by choosing one output for each input. How many leaves would the corresponding decision tree have?
Practice 10: Identify the Error
A student draws a tree for selecting two different people from a group of \(5\), but gives every first-stage branch \(5\) second-stage branches. What is wrong?
Practice Answers
Practice 1
\[ \boxed{4\cdot3=12}. \]Practice 2
\[ \boxed{2\cdot5\cdot3=30}. \]Practice 3
\[ \boxed{4+7+2=13}. \]Practice 4
The first stage has \(6\) choices and the second has \(5\) remaining choices:
\[ \boxed{6\cdot5=30}. \]Practice 5
\[ \boxed{2^4=16}. \]Practice 6
\[ \boxed{1+5=6}. \]Practice 7
Package \(A\):
\[ 3\cdot2=6. \]Package \(B\):
\[ 5\cdot4=20. \]Therefore,
\[ \boxed{6+20=26}. \]Practice 8
\[ \boxed{2^7=128}. \]Practice 9
Each of the \(3\) domain elements has \(4\) possible outputs:
\[ \boxed{4^3=64}. \]Practice 10
After the first person is selected, that person cannot be selected again. Each first-stage branch should therefore have only \(4\) valid second-stage branches.
The correct number of leaves is
\[ \boxed{5\cdot4=20}. \]What to Remember
A decision tree represents a counting process through branches and complete paths.
- The root represents the starting point.
- Branches represent choices.
- Internal nodes represent partial outcomes or intermediate states.
- Leaves represent complete outcomes.
- Regular branching often leads to multiplication.
- Unequal branch totals are often added.
- Restrictions appear as missing or altered branches.
- Each valid outcome should correspond to exactly one complete path.
Where We Go Next
Decision trees help make the structure of a counting problem visible, but many counting problems are easier to solve by counting everything first and then removing the outcomes that violate a condition.
The next lesson, Complementary Counting, develops this strategy by using the complement of a desired set of outcomes.