CS210 · Annotated SlidesTrees — Trees
Trees · Annotated slides

Trees

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

Slide text Study notes Highlight: key words Tips, tricks & traps Seen again elsewhere How it can come up
Slide 1: Presentation for use with the textbook Data Structures and Algorithms in Java, 6
Exam weight Low
    Slide 2: What is a Tree
    Exam weight Low
      Slide 3: Tree Terminology
      Exam weight High
      1. Root, internal and external (leaf) nodes, ancestors, descendants, depth (from root), height (max depth), subtree.
      🎯 How this can come up · 1 question
      MCQ

      The height of a tree is:

      Slide 4: Tree ADT
      Exam weight Low
        Slide 5: Java Interface
        Exam weight Low
          Slide 6: as visitrootuss
          Exam weight Low
          1. Preorder: node, then children. Postorder: children, then node.
          Slide 7: axioms.in
          Exam weight Low
            Slide 8: A
            Exam weight Low
              Slide 9: Binary Trees
              Exam weight Low
              1. Binary tree: each node has at most two children (left, right). Proper: 0 or 2 children.
              Slide 10: n 2 d
              Exam weight Low
                Slide 11: 2x a t b
                Exam weight Low
                  Slide 12: night
                  Exam weight Low
                    Slide 13: Decision Tree
                    Exam weight Low
                      Slide 14: Properties of Proper Binary Trees
                      Exam weight High
                      1. Proper binary tree: e = i + 1 (leaves = internal + 1); h ≤ i; e ≤ 2ʰ.
                      🎯 How this can come up · 1 question
                      MCQ

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

                      Slide 15: BinaryTree ADT
                      Exam weight Low
                        Slide 16: L Root R
                        Exam weight High
                        1. Inorder: left, node, right.
                        🎯 How this can come up · 1 question
                        MCQ

                        Inorder traversal of a BST gives the keys:

                        Slide 17: Print Arithmetic Expressions
                        Exam weight Low
                        1. Print an arithmetic expression: inorder with parentheses. Evaluate it: postorder.
                        Slide 18: Evaluate Arithmetic Expressions
                        Exam weight Low
                          Slide 19: Euler Tour Traversal
                          Exam weight Low
                          1. Euler tour: visit each node on the left, from below, and on the right (generalizes all three).
                          Slide 20: Linked Structure for Trees
                          Exam weight Low
                            Slide 21: A
                            Exam weight Low
                              Slide 22: Linked Structure for Binary Trees
                              Exam weight Low
                                Slide 23: Array-Based Representation of Binary Trees
                                Exam weight High
                                1. Array representation: root at 1 (or 0); children of node i at 2i and 2i + 1 (with root at 1).
                                🎯 How this can come up · 1 question
                                MCQ

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

                                Slide 24: Slide 24
                                Exam weight Low

                                  25
                                  Exam weight Low