Kotlinlearncs.online LogoJava

    ← Prev

    Index

    Next →

    Kotlin
    Java

    • Trees and Recursion : 49

    • Trees : 48

    • Recursion : 47

    • Lists Review and Performance : 46

    • Linked Lists : 45

    • Algorithms and Lists : 44

    • Lambda Expressions : 43

    • Anonymous Classes : 42

    • Practice with Interfaces : 41

    • Implementing Interfaces : 40

    • Using Interfaces : 39

    • Working with Exceptions : 38

    • Throwing Exceptions : 37

    • Catching Exceptions : 36

    • References and Polymorphism : 35

    • References : 34

    • Data Modeling 2 : 33

    • Equality and Object Copying : 32

    • Polymorphism : 31

    • Inheritance : 30

    • Data Modeling 1 : 29

    • Static : 28

    • Encapsulation : 27

    • Constructors : 26

    • Objects, Continued : 25

    • Introduction to Objects : 24

    • Compilation and Type Inference : 23

    • Practice with Collections : 22

    • Maps and Sets : 21

    • Lists and Type Parameters : 20

    • Imports and Libraries : 19

    • Multidimensional Arrays : 18

    • Practice with Strings : 17

    • null : 16

    • Algorithms and Strings : 15

    • Strings : 14

    • Functions and Algorithms : 13

    • Practice with Functions : 12

    • More About Functions : 11

    • Errors and Debugging : 10

    • Functions : 9

    • Practice with Loops and Algorithms : 8

    • Algorithms I : 7

    • Loops : 6

    • Arrays : 5

    • Compound Conditionals : 4

    • Conditional Expressions and Statements : 3

    • Operations on Variables : 2

    • Variables and Types : 1

    • Hello, world! : 0

    Trees

    public class BinaryTree {
    private Object value;
    private BinaryTree left;
    private BinaryTree right;
    public BinaryTree(Object setValue) {
    value = setValue;
    }
    public Object getValue() {
    return value;
    }
    public BinaryTree getLeft() {
    return left;
    }
    public Object getRight() {

    This lesson introduces a new data structure: trees. Trees are extremely useful, both for modeling certain types of data, and for enabling certain algorithms. They are also great for practice with recursion! Let’s do this…

    Warm Up Debugging Challenge
    Warm Up Debugging Challenge

    But… you knew it! Let’s warm up with another debugging challenge!

    What is a Tree?
    What is a Tree?

    Wikipedia defines a (computer science) tree as:

    In computer science, a tree is a widely used abstract data type that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.

    Let’s look at some diagrams that will help visualize this new data structure, and introduce some important terminology.

    What are Trees For?
    What are Trees For?

    Trees can be used to model a variety of hierarchical data. Examples include:

    Let’s look at these example a bit more:

    We’ll also see ways that trees can be used to store a collection of items in ways that enable certain efficient algorithms. For example, by storing data in a tree, we can enable more efficient search algorithms than the O(n) scans of arrays we’ve seen so far. We’ll get there!

    Binary Trees
    Binary Trees

    Most of the work with trees that we’ll be doing is on a specific type of tree called a binary tree. Binary trees are so named because each node has up to two children, but no more.

    Let’s develop the BinaryTree class that we’ll use in class and that we’ll use on upcoming homework problems. Note that this is available in the playground environments and homework as cs125.trees.BinaryTree. As a way of reviewing object design and references, let’s walk through the process of designing this class:

    // BinaryTree class

    Recursion on Trees
    Recursion on Trees

    Last time we introduced recursion, a problem solving technique that works by breaking down large problems into smaller pieces, solving them, and then combining the results. Binary trees are a great fit for recursion! Let’s see why:

    In addition, compared to lists and arrays and Strings, trees are hard to work with using iterative solutions! Recursion is a much better approach…

    Recursive Tree Sum
    Recursive Tree Sum

    Let’s get some practice with recursion on trees. We’ll take a tree filled with integer values and determine the sum of all the values it stores. Along the way, we’ll look at several recursive approaches, and begin to develop some of the patterns that we’ll use working recursively with binary trees.

    // BinaryTree Sum

    Recursive Tree Size
    Recursive Tree Size

    To help you prepare for our next homework problem, let’s discuss the recursive approach to counting the number of nodes in a tree.

    Solve: BinaryTree Negative Sum (Practice)

    Created By: Geoffrey Challen
    / Version: 2021.10.0

    Create a public class named BinaryTreeNegativeSum with a single class method named negativeSum. negativeSum accepts a BinaryTree<Integer>, that is a BinaryTree containing Integer values. Return the sum of all the negative values in the tree.

    For reference, cs125.trees.BinaryTree has the following public properties:

    Computational Complexity
    Computational Complexity

    Let’s pause for a moment to discuss how we evaluate the complexity of your homework submissions, and what you can do to improve your code when we indicate that it is too complicated. First, a practice problem to work on. Once you’ve solved this, the solution walkthrough will show what happens to an overly-complex submission, and discuss how to reduce the complexity of your code.

    The practice problem below looks like a regular practice problem, but it introduces a new way in which we’ll begin scoring your homework solutions: evaluating their complexity. Starting now there is 1 point out of 10 you’ll earn for not submitting an overly-complex solution. Solve the problem and then watch a solution walkthrough to learn more!

    Created By: Geoffrey Challen
    / Version: 2021.7.0

    Declare and implement a function called sumIsOdd. sumIsOdd should accept two int arguments and return true if their sum is odd and false otherwise. You will probably want to consider using the remainder operator (%) to complete this problem.

    Solve: Binary Tree Size

    Created By: Geoffrey Challen
    / Version: 2020.11.0

    Create a public class BinaryTreeSize that provides a single static method size. size accepts a cs125.trees.BinaryTree<?>, a BinaryTree that can contain any value, and returns the number of nodes it contains. You'll want to count recursively, identifying both a base case and a recursive step.

    For reference, cs125.trees.BinaryTree has the following public properties:

    Don't overthink this! Like many recursive algorithms, the solution is elegant and simple: 4 lines total if you do it right. You'll also need to import cs125.trees.BinaryTree for this and similar problems.

    More Practice

    Need more practice? Head over to the practice page.