CS210 · Trees · Annotated SlidesTrees
Original
Overview

Trees

Tree terminology and ADT, preorder/postorder traversals, binary trees and their properties, inorder traversal, expression trees, Euler tour, and linked and array representations.

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 25 slides
  1. 1 Presentation for use with the textbook Data Structures and Algorithms in Java, 6
  2. 2 What is a Tree
  3. 3 Tree Terminology
  4. 4 Tree ADT
  5. 5 Java Interface
  6. 6 as visitrootuss
  7. 7 axioms.in
  8. 8 A
  9. 9 Binary Trees
  10. 10 n 2 d
  11. 11 2x a t b
  12. 12 night
  13. 13 Decision Tree
  14. 14 Properties of Proper Binary Trees
  15. 15 BinaryTree ADT
  16. 16 L Root R
  17. 17 Print Arithmetic Expressions
  18. 18 Evaluate Arithmetic Expressions
  19. 19 Euler Tour Traversal
  20. 20 Linked Structure for Trees
  21. 21 A
  22. 22 Linked Structure for Binary Trees
  23. 23 Array-Based Representation of Binary Trees
  24. 24 Slide 24
  25. 25 Slide 25
Slide 1 / 25

Presentation for use with the textbook Data Structures and Algorithms in Java, 6

Slide 1: Presentation for use with the textbook Data Structures and Algorithms in Java, 6
Slide 2 / 25

What is a Tree

Slide 2: What is a Tree
Slide 3 / 25

Tree Terminology

Slide 3: Tree Terminology

Exam angle

PredictionQ1

The height of a tree is:

Slide 4 / 25

Tree ADT

Slide 4: Tree ADT
Slide 5 / 25

Java Interface

Slide 5: Java Interface
Slide 6 / 25

as visitrootuss

Slide 6: as visitrootuss
Slide 7 / 25

axioms.in

Slide 7: axioms.in
Slide 8 / 25

A

Slide 8: A
Slide 9 / 25

Binary Trees

Slide 9: Binary Trees
Slide 10 / 25

n 2 d

Slide 10: n 2 d
Slide 11 / 25

2x a t b

Slide 11: 2x a t b
Slide 12 / 25

night

Slide 12: night
Slide 13 / 25

Decision Tree

Slide 13: Decision Tree
Slide 14 / 25

Properties of Proper Binary Trees

Slide 14: Properties of Proper Binary Trees

Exam angle

PredictionQ1

A proper binary tree with 7 internal nodes has how many leaves?

Slide 15 / 25

BinaryTree ADT

Slide 15: BinaryTree ADT
Slide 16 / 25

L Root R

Slide 16: L Root R

Exam angle

PredictionQ1

Inorder traversal of a BST gives the keys:

Slide 17 / 25

Print Arithmetic Expressions

Slide 17: Print Arithmetic Expressions

Notes

  1. Print an arithmetic expression: inorder with parentheses. Evaluate it: postorder.

Slide 18 / 25

Evaluate Arithmetic Expressions

Slide 18: Evaluate Arithmetic Expressions
Slide 19 / 25

Euler Tour Traversal

Slide 19: Euler Tour Traversal
Slide 20 / 25

Linked Structure for Trees

Slide 20: Linked Structure for Trees
Slide 21 / 25

A

Slide 21: A
Slide 22 / 25

Linked Structure for Binary Trees

Slide 22: Linked Structure for Binary Trees
Slide 23 / 25

Array-Based Representation of Binary Trees

Slide 23: Array-Based Representation of Binary Trees

Exam angle

PredictionQ1

With the root at index 1, the children of node i are at:

Slide 24 / 25

Slide 24

Slide 24: Slide 24
Slide 25 / 25

Slide 25

Slide 25: Slide 25