TRT
Sign in

Core · Module 10 · Lesson 1 of 5

Vocabulary and traversals

A tree is nodes joined by parent-child links with no cycles. Visiting every node is a choice of order: before the children, between them, or after them. Each order fits different jobs.

Pro — members onlyAbout 13 minutes

By the end you can

  • Use tree vocabulary precisely: root, child, leaf, depth, height, subtree
  • Traverse a binary tree in preorder, inorder and postorder, recursively and with a stack
  • Choose the traversal order that a task needs

Builds on Recursion vs iteration.

01 · A question first

A folder tree, an HTML page and the expression (2 + 3) × 4 are all trees. Copying the folders, totaling their sizes and evaluating the expression each need the nodes visited in a different order. Which order does each need, and why?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

  • What a tree is
  • Representing a tree
  • Three depth-first orders
  • Which order for which job
  • Traversing without recursion
  • Pseudocode & Multi-Language Implementations (C++, Java, Python)
  • Complexity Derivation, Edge Cases & Common Mistakes
See plansAlready a member? Sign in

03 · Practice

Practice · easy · LeetCodeMaximum depth of binary treeReturn the number of nodes on the longest root-to-leaf path, recursively and with a level-order traversal.Practice · easy · LeetCodeInvert binary treeMirror a binary tree by swapping every node's left and right children.Practice · easy · LeetCodeBinary tree inorder traversalReturn the inorder traversal of a binary tree, first recursively and then iteratively with an explicit stack.Practice · medium · LeetCodeConstruct binary tree from preorder and inorder traversalRebuild a binary tree from its preorder and inorder traversals, using the root from preorder to split the inorder list.

Asked in interviews

Something wrong with this lesson? Report a problem