SEM 6 › Discrete Mathematics › Week 13
Discrete Mathematics · Week 13

Decision Trees, Tree Traversal & Spanning Trees

Decision trees as maps of choices and outcomes (drawing, evaluating with expected values, pros and cons), preorder and postorder traversal of ordered rooted trees, and spanning trees with their use in IP multicasting.

ITE38222 videos · 24 min📄 Lesson 12 - Trees_2.pdf

▶Lecture videos

Click any timestamp — here or inside the notes — to jump the video to that moment. Your position is remembered.

Video Lecture 1 – Decision trees

What a decision tree is, the buy-a-car example, drawing with squares and circles, extra advantages, disadvantages and applications, and the badminton tree.

00:01Lesson 12.2: decision trees, traversal, spanning trees01:29A decision tree weighs possible actions01:44Informal example: should I buy a car?03:02Definition: rooted tree, internal vertex = decision04:44Drawing: lines = options, squares = decisions, circles = uncertainty05:23Seven extra advantages06:38Disadvantages: overfitting, instability, many classes07:14When to use decision trees, and application areas08:21Example: play badminton?

Video Lecture 2 – Expected values, traversal & spanning trees

The new-product expected-value exercise, preorder and postorder traversal, and spanning trees.

00:08Self-assessment 2: launch a new product?01:28Draw the decision tree: develop or not02:33EV at A = $780,000; EV at C = 0.7 × A + 0.3 × B03:43Tree traversal: visit every node exactly once04:57Preorder: start with the root07:51Postorder: subtrees first, root last10:03Spanning trees: G is connected11:29Connected ⇔ has a spanning tree

1Decision trees

What is a decision tree?

A decision tree is a map of the possible outcomes of a series of related choices. It lets a person or organisation weigh possible actions against one another based on their costs, probabilities and benefits.

  • It uses a tree-like model of decisions: it starts at a single node that branches into possible outcomes, and each outcome leads to further nodes.
  • It can drive informal discussion or map out an algorithm that predicts the best choice mathematically.
  • A rooted tree is a tree in which one special node, the root, is singled out.
Should I buy a car? 01:44
  • Should I buy a car? → Do I have good public transport?
  • Yes → don't buy
  • No → buy
  • If I decide not to buy → Do I often travel outside my city?
  • Yes → consider buying
  • No → don't buy

The tree starts at one node (the question), branches into outcomes (yes / no), and each outcome leads to further nodes.

Definition 1

A rooted tree in which each internal vertex corresponds to a decision, with a subtree at these vertices for each possible outcome of the decision, is called a decision tree.

Drawing your own decision tree

Symbol Means
Square ■ A decision to be made
Circle ● An uncertain outcome (chance)
Nothing / triangle ▲ A final result
  1. Draw the decision as a small square on the left
  1. Draw one line per option to the right and label it
  1. At each line's end: another decision → square; uncertain → circle; result → nothing
  1. From squares draw the choices; from circles draw the possible outcomes
  1. Keep going until every path ends in a result

Evaluating a decision tree

  1. Estimate the value of each final outcome.
  2. At each circle, assign a probability to each outcome. They must add up to 100% (or 1).
  3. Calculate: multiply each end value by its probability and add them up at each circle. Subtract any costs along the way to get the net value.
  4. Choose the option with the highest value.
From the lesson

The probability of promotion is 0.7 and it's worth 80,000, so that branch contributes 0.7 × 80,000 = 56,000.

Expected value at a chance node = Σ (probability × value)
Self-assessment 2: launch a new product? 00:08

The tree has two choices: develop or don't develop (profit $0). Under "develop" there's a chance node for success / failure, then chance nodes for high / medium / low and sell / worthless 01:28.

R&D costs $400,000. Success 70%, failure 30%.

If successful (profits for two years):

Popularity Probability Profit per year Two-year profit Prob × profit
High 0.2 $500,000 $1,000,000 $200,000
Medium 0.5 $400,000 $800,000 $400,000
Low 0.3 $300,000 $600,000 $180,000
EV(success) $780,000

If it fails: 0.6 × $50,000 + 0.4 × $0 = $30,000

Launch: 0.7 × 780,000 + 0.3 × 30,000 = 546,000 + 9,000 = $555,000

Net of R&D: 555,000 − 400,000 = $155,000 > 0

Recommendation: develop and launch the product, because its expected net value is positive (+$155,000) compared with $0 for not launching.

🧪 Try it — Expected value calculator

Advantages and disadvantages

Advantages Disadvantages
Classify without much computation Error-prone with many classes and few training examples
Handle both continuous and categorical variables Computationally expensive to train (growing the tree is costly)
Clearly show which fields matter most for prediction

The lecture adds more 05:23:

More advantages

  1. Easy to understand, even for people from non-analytical backgrounds
  2. Useful in data exploration: one of the fastest ways to find the most significant variables and relations between them
  3. Less effort needed from users for data preparation
  4. Less data cleaning required
  5. Data type is not a constraint
  6. Non-parametric: no assumptions about the space distribution or classifier structure
  7. Non-linear relationships between parameters don't affect performance

More disadvantages 06:38

  1. Overfitting: over-complex trees that don't generalise well
  2. Unstable: small variations in the data can produce a completely different tree
  3. Calculations get complex with many class labels

When to use a decision tree 07:14:

  1. The decision maker has an objective (e.g. maximise profit, optimise cost)
  2. There are several courses of action
  3. There's a calculable measure of benefit for the alternatives
  4. There are events beyond the decision maker's control (e.g. environmental factors)
  5. There's uncertainty about which outcome will actually happen

Application areas: medicine, planning, pharmacology, molecular biology, astronomy, biomedical engineering, production and manufacturing.

Example 13.1: play badminton?

To decide whether to play on Saturday, you record temperature, wind, humidity and outlook (sunny, cloudy, rainy) for the last ten days in a lookup table.

  • Problem: Saturday's weather might not match any row of the table.
  • A decision tree solves this. It considers every path to the final decision.
  • Each node is an attribute, each branch is an outcome of that attribute, and each leaf is the final decision (play / don't play).
The badminton tree 08:49
  • Outlook = sunny → depends on humidity: high → don't play; normal → play
  • Outlook = cloudy → play (no other variable matters)
  • Outlook = rainy → depends on wind: strong → don't play; weak → play

Temperature never matters in this tree.

Self-assessment 1: sequences of A's and B's

List all sequences of length six with no two adjacent A's and never three adjacent B's, with the leaves in alphabetical order.

Build the tree one letter at a time, cutting a branch as soon as it creates AA or BBB. There are 9 leaves:

ABABAB · ABABBA · ABBABA · ABBABB · BABABA · BABABB · BABBAB · BBABAB · BBABBA

2Tree traversal

Tree traversal is a form of graph traversal: visiting each node of a tree exactly once 03:43. Ordered rooted trees store information and can represent expressions (numbers, variables, operations). To use the data, we need procedures that visit every vertex: traversal algorithms. Both are defined recursively.

Preorder: root first

Visit the root r, then traverse T₁ in preorder, then T₂, … then Tₙ (subtrees left to right).

Postorder: root last

Traverse T₁ in postorder, then T₂, … then Tₙ, and finally visit the root r.

Definition 2 (postorder)

Let T be an ordered rooted tree with root r. If T is only r, then r is the postorder traversal. Otherwise, with subtrees T₁, …, Tₙ from left to right, the postorder traversal traverses T₁ … Tₙ in postorder and ends by visiting r.

Example 13.2.1

The tree T in the lesson has root a with children b, c, d. Then:

  • b → e, f
  • e → j, k
  • k → n, o, p
  • d → g, h, i
  • g → l, m
Preorder of T

a, b, e, j, k, n, o, p, f, c, d, g, l, m, h, i

Correction to the PDF

The PDF lists the preorder as "a, b, e, j, k, n, o, p, j, c, …". The second j should be f. After finishing the subtree at e, you visit b's next child, f.

Postorder of the same tree

j, n, o, p, k, e, f, b, c, l, m, g, h, i, d, a

🧪 Try it — Traversal explorer (tree T from Example 13.2.1)
Quick trick
  • Preorder: walk around the tree from the root, counter-clockwise, and list each vertex the first time you pass it.
  • Postorder: list each vertex the last time you pass it.

3Spanning trees

Definition

Let G be a simple graph. A spanning tree of G is a subgraph of G that is a tree containing every vertex of G.

Finding one: remove edges from circuits

Example 13.3.1

G is connected but not a tree, because it has simple circuits.

  1. Remove {a, e}: one circuit is gone, and G stays connected with every vertex.
  2. Remove {e, f}: a second circuit is gone.
  3. Remove {c, g}: no simple circuits are left.

The result is a spanning tree of G.

Theorem 1

A simple graph is connected if and only if it has a spanning tree.

A tree with n vertices has n − 1 edges, so from a connected graph with n vertices and m edges you must remove m − (n − 1) = m − n + 1 edges to get a spanning tree.
🧪 Try it — Edges to remove

Application: IP multicasting (Example 13.3.2)

Unicasting

Send a separate copy to each receiving computer. Inefficient: many copies of the same data cross the network.

IP multicasting

Send data once along a spanning tree to all receivers. Efficient and fast.

  • Data must never loop: once it reaches a router it should never return there. Loops are circuits, so the routers build a spanning tree.
  • Vertices: the multicast source, the routers, and the subnetworks with receiving computers.
  • Edges: the links between computers and/or routers.
  • Root: the multicast source.
  • Leaves: the subnetworks containing receiving computers.
Exam focus
  • Decision tree: draw it with squares and circles, show probability × value at each chance node, subtract costs, and give a clear recommendation.
  • Traversal: write the full vertex list, and check that every vertex appears exactly once.
  • Spanning tree: remove one edge from each circuit; a tree with n vertices has n − 1 edges.

4Quick revision sheet

Concept Remember it as
Decision tree Map of outcomes of related choices; internal vertex = decision, subtree per outcome
Symbols Square = decision · circle = uncertainty · nothing/triangle = result
Evaluate Probability × value at chance nodes; subtract costs; pick the highest
Product example EV = 0.7 × 780,000 + 0.3 × 30,000 = 555,000; net +155,000 → launch
Pros Little computation; continuous + categorical; shows important fields
Cons Errors with many classes/few examples; expensive to train; overfitting; unstable
A/B exercise 9 sequences (no AA, no BBB)
Preorder Root, then subtrees left to right: a b e j k n o p f c d g l m h i
Postorder Subtrees left to right, then root: j n o p k e f b c l m g h i d a
Spanning tree Subgraph that's a tree containing every vertex
Theorem 1 Connected ⇔ has a spanning tree
Edges to remove m − n + 1
Multicasting Spanning tree, no loops; root = source, leaves = receiving subnetworks

?Self-check quiz

18 questions on this week. Answer them all, then press Check my answers. Your best and latest scores are saved and shown on the subject page.

← PreviousTrees & Applications of Trees