Tree Traversal Methods | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 11.2 Free with a free account

Tree Traversal Methods

Discrete Mathematics · Chapter 11: Trees, Spanning Trees, and Minimum Cost NetworksSection 11.2 · lesson 72 of 879 min · free with a free account

← Trees: Properties and DefinitionsNext lesson: Sorting with Trees: Benefits and Limitations →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

4 systematic ways to visit every node exactly once.

  • Trace pre-order, in-order and post-order
  • Explain why in-order needs a binary tree
  • Compute a level-order traversal with a queue
  • Match each order to the job it does best

Transcript

Everything said in the video, section by section (1,309 words). Read along, or search it.

Trees, Spanning Trees, and Minimum Cost Networks

Tree Traversal Methods

Once data lives in a tree, almost every task starts by visiting its nodes in some order. This section develops four traversal orders: pre-order, in-order, post-order and level-order. Each visits every node exactly once, and each is useful for a different job.

The Opening Problem

One Expression, 3 Jobs

Every calculator app, spreadsheet formula engine and compiler has to make sense of an expression like two plus five, times nine minus six. Internally, these systems almost never work with the flat string of characters. They parse it into a tree, with each operator as a node, and its operands as children. Once the expression is a tree, very different jobs, like printing it back out, evaluating it to a number, or saving it for another program, all come down to one question. In what order should the nodes be visited? Visiting every node exactly once, by a systematic rule, is called a tree traversal.

11.2.1

3 Depth-First Orders

Traversals are defined recursively. In a binary tree, every node has at most two children, a left child and a right child. Take a tree rooted at v, with a left subtree and a right subtree. Either may be empty, and an empty subtree just contributes nothing. Pre-order visits v first, then traverses the left subtree, then the right. In-order traverses the left subtree, then visits v, then traverses the right. Post-order traverses the left subtree, then the right, and visits v last. The only difference is when the root is visited. All three are depth-first. Each recursive call follows one subtree all the way down before backtracking to the other.

Worked Example

Pre-order on (2 + 5) × (9 − 6)

Here's the expression tree. The root is the outermost operator, times. Its left child is the subtree for two plus five, and its right child is the subtree for nine minus six. Pre-order visits each node before either of its subtrees. So record times. Then go left into the plus subtree: record plus, then two, then five. Then go right into the minus subtree: record minus, then nine, then six. The pre-order sequence is times, plus, two, five, minus, nine, six. Read left to right, that's prefix notation, also called Polish notation. Each operator appears immediately before its two operands.

Worked Example

In-order and Post-order

In-order visits the left subtree, then the root, then the right subtree, at every level. The left subtree gives two, plus, five. Then comes the root, times. Then the right subtree gives nine, minus, six. That's exactly the original infix sequence of tokens. But it's only the tokens, not the parentheses. On its own, it can't distinguish the original expression from two plus five times nine minus six, with no grouping. Post-order visits both subtrees before the root. That gives two, five, plus, then nine, six, minus, and finally times. That's postfix notation, or Reverse Polish, and it's unambiguous with no parentheses at all. Read left to right, pushing operands onto a stack. Each operator combines the two most recent values. Push two and five, and plus gives seven. Push nine and six, and minus gives three. Then times combines seven and three, giving twenty-one. That matches the original expression.

Listing 1

3 Functions, One Line Moved

In Python, the three functions are nearly identical. Each returns immediately on an empty subtree. Otherwise, it records the node's value, and recurses on the left and right children. The only difference is where the recording line sits. First for pre-order, between the two calls for in-order, and last for post-order. Run on the expression tree, using a letter x for times, they return exactly the three sequences we traced.

11.2.2

Why In-order Needs Left and Right

These definitions lean on the binary structure more than they first appear to. Pre-order and post-order generalize easily to a general, or k-ary, tree, where a node may have any number of children. Visit the root, then recurse on each child from left to right. Or recurse on each child first, then visit the root. Take a project folder, Project, holding three subfolders, Docs, Src and Tests. Docs holds one file, Guide. General pre-order gives Project, Docs, Guide, Src, Tests. General post-order gives Guide, Docs, Src, Tests, and finally Project. In-order doesn't survive. Its rule says visit the root between the left and right subtrees. With three children, there's no canonical place for the root. After the first child, or after the second? Either choice is arbitrary.

Listing 2

Pre-order on a General Tree

For a general tree, each node keeps a list of children instead of fixed left and right references. Pre-order records the node, then loops over its children from left to right, recursing on each. On the project tree, it returns Project, Docs, Guide, Src, Tests. And the same loop would work unchanged, whether Project had two children or twenty.

11.2.3

Level-order: Breadth-First

The three orders so far all go deep before going wide. Level-order does the opposite. It visits every node at depth zero, then every node at depth one, then depth two, and so on, left to right within each level. That's a breadth-first strategy. It's computed with a first-in, first-out queue. Put the root in the queue. Then repeatedly remove the front node, visit it, and add its children to the back, until the queue is empty. On the expression tree, the queue starts with times. Remove times, and add plus and minus. Remove plus, and add two and five. Remove minus, and add nine and six. The last four are leaves, so they're just removed and visited in order. The level-order sequence is times, plus, minus, two, five, nine, six.

Listing 3

Level-order With a Queue

Here's level-order in Python, using a double-ended queue. Each step removes a node from the front, skips it if it's empty, records it, and adds its two children to the back. On the expression tree, it returns times, plus, minus, two, five, nine, six. Unlike the depth-first orders, it's naturally iterative. It's the right choice whenever a task processes a tree layer by layer. For example, rendering a user interface one nesting level at a time, or counting the nodes within some number of steps of the root.

Table 1

4 Orders, One Tree

Here are all four sequences on the same tree. The tree never changes. Only the visiting order does. And all four run in theta of n time on a tree with n nodes. For the depth-first orders, each node is handled in exactly one call, which does a constant amount of work of its own. For level-order, each node is added to the queue once and removed once. So they differ in the order of visiting, not in cost.

Table 2

Which Order for Which Job

So which order fits which job? Pre-order writes each parent before its children, so it's the natural way to serialize or copy a tree for easy reconstruction. In-order recovers the infix tokens of an expression. It's the one order that works only for binary trees. Post-order handles bottom-up work, like evaluating an expression, or any total that needs the children's results before the parent's. And level-order processes a tree one depth level at a time. For the calculator, post-order evaluates the expression to twenty-one, pre-order saves it in prefix form, and in-order redisplays something like the original. In-order's best-known use, sorting with a binary search tree, comes in section eleven point three.

Takeaways

Same Tree, Different Order

To summarize. A tree traversal visits every node exactly once, by a systematic rule. Pre-order, in-order and post-order are depth-first, and differ only in where visiting the root falls. In-order is binary-tree-specific, because its rule assumes exactly two subtrees. Pre-order, post-order and level-order all generalize. Level-order is breadth-first, driven by a first-in, first-out queue. And all four run in linear time. Here's something to think about. Take a root A with exactly one child, B. Whether B is a left child or a right child, pre-order gives A, B, and post-order gives B, A. Only in-order tells the two trees apart. In fact, with distinct labels, in-order together with pre-order or post-order always pins down a binary tree. What is it about in-order's rule that resolves left versus right, when the other two miss it?

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Tree Traversal Methods

What is the difference between pre-order, in-order, and post-order traversal?
The three differ only in when the root is visited relative to its left and right subtrees. Pre-order visits the root, then left, then right. In-order goes left, root, right. Post-order goes left, right, root. All three are depth-first, following one subtree all the way down before backtracking.
Why does in-order traversal only work on binary trees?
In-order places the root between its left and right subtrees, which assumes exactly two subtrees. A node with three children has no canonical spot for the root: after the first child or after the second? Either choice is arbitrary. Pre-order and post-order avoid this by visiting the root first or last.
How do you do a level-order traversal with a queue?
Put the root in a first-in, first-out queue, then repeatedly remove the front node, visit it, and add its children to the back until the queue is empty. For the tree of (2+5)\times(9-6), this gives \times, +, -, 2, 5, 9, 6, which visits nodes level by level, left to right.
Which traversal order should I use to evaluate an expression tree?
Use post-order, because evaluation needs each node's children computed before the node itself. For (2+5)\times(9-6), post-order gives 2, 5, +, 9, 6, -, \times. Reading with a stack, + gives 7, - gives 3, and \times gives 21. Pre-order instead gives prefix notation, and in-order gives the infix tokens without parentheses.

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Discrete Mathematics cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →