Skip to content
Ameen Abozaid
Englishالعربية
BEG-042

Trees

  • 6 Lessons
  • 72 min of reading
  • 4 h practice (estimate)
Start module
On this page 8 topics

Overview

Topics

  • Binary trees
  • BST
  • traversal
  • heap fundamentals

Learn first

72 min of reading · 4 h of practice (estimate)

Learning outcomes

  1. Implement a binary search tree with insert, search, and in-order traversal.
  2. Perform pre-, in-, post-order, and level-order traversal.
  3. Explain why an unbalanced BST degrades to O(n) and what balanced trees solve (conceptually).
  4. Explain a binary heap and use PriorityQueue.

Lessons

  1. 01Trees and terminology12 min read
  2. 02Binary search trees12 min read
  3. 03Traversals12 min read
  4. 04Balance (concept only)12 min read
  5. 05Heaps and PriorityQueue12 min read
  6. 06Demo: BST insert and traversals, step by step12 min read

Lab and exercises

Lab

BEG-042-LAB1 · BST and task scheduler

Outcomes: 1–4 · Time: ~4 h

  1. Implement a BST with insert, contains, and all four traversals returning lists.
  2. Insert sorted values and show the height problem.
  3. Build a task scheduler with PriorityQueue<Task> (priority, then name) that always runs the most urgent task next.

Acceptance: tests pass; traversal outputs correct.

Exercises (assessment: implementation plus traversal exercises)

IDOutcomeTask
BEG-042-EX011Insert 50, 30, 70, 20, 40, 60, 80 into a BST and draw it. Is 45 found, and by which path?
BEG-042-EX021Write contains(Node, int) recursively, including the null case.
BEG-042-EX032For the tree from EX01, write pre-, in-, post-, and level-order outputs.
BEG-042-EX043Explain in three sentences why inserting 1, 2, 3, 4, 5 into a BST is a problem and what balanced trees do.
BEG-042-EX054Show a min-heap after adding 9, 4, 7, 1 (as an array); then what poll() returns twice.
BEG-042-EX064Explain two differences between a BST and a heap.
Show solutions
  • EX01 Root 50; left 30 (20, 40); right 70 (60, 80). 45 is not found: 50, left to 30, right to 40, right of 40 is null.
  • EX02 if (n == null) return false; if (v == n.value) return true; return v < n.value ? contains(n.left, v) : contains(n.right, v);
  • EX03 Pre: 50 30 20 40 70 60 80. In: 20 30 40 50 60 70 80. Post: 20 40 30 60 80 70 50. Level: 50 30 70 20 40 60 80.
  • EX04 Sorted inserts always go right, giving a chain of height n, so search is O(n). Balanced trees rotate nodes to keep the height near log n, so operations stay O(log n).
  • EX05 One valid layout: [1, 4, 7, 9] (insert 9; add 4 and swap up -> 4, 9; add 7 -> 4, 9, 7; add 1 and swap up twice -> 1, 4, 7, 9). poll() returns 1, then 4.
  • EX06 A BST keeps left < node < right and supports sorted traversal and search in O(log n) when balanced; a heap only guarantees parent <= children, gives the minimum in O(1), and cannot be searched quickly or iterated in order.

Quiz

Outcomes: O1 BST · O2 traversals · O3 balance · O4 heaps and PriorityQueue.

A self-check for you: nothing is graded, saved or sent anywhere. Choose an answer, then check it. You can try again as often as you like.

  1. 1In a BST, values smaller than a node are found in its:O1
  2. 2A node with no children is a:O1
  3. 3Recursive BST code should first check:O1
  4. 4In-order traversal of a BST gives:O2
  5. 5Pre-order visits:O2
  6. 6Level-order traversal uses a:O2
  7. 7Inserting 1, 2, 3, 4, 5 in order into a plain BST makes search:O3
  8. 8Which JDK class uses a self-balancing tree?O3
  9. 9The root of a min-heap is:O4
  10. 10A default PriorityQueue<Integer> poll() returns the:O4

Practical part

Implementation of the BST and task scheduler (BEG-042-LAB1) plus traversal exercises (BEG-042-EX01 to EX06). Pass: tests pass, all four traversal outputs correct, and at least 8 of 10 quiz answers correct.

Common mistakes

Missing null checks in recursion; confusing heap with BST.

Assessment

Implementation plus traversal exercises.

Career relevance

B-tree indexes (MID-012), TreeMap choices.

Type to search levels, phases, modules and lessons.