Kotlinlearncs.online LogoJava

    ← Prev

    Index

    Next →

    Kotlin
    Java

    • Sorting Algorithms : 51

    • Practice with Recursion : 50

    • 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

    • Companion Objects : 28

    • Encapsulation : 27

    • Constructors : 26

    • Objects, Continued : 25

    • Introduction to Objects : 24

    • Compilation and Immutability : 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

    Practice with Recursion

    import cs125.trees.BinaryTree
    fun treeDepth(tree: BinaryTree<*>?): Int {
    return 0
    }
    assert(treeDepth(BinaryTree(0, 1, 2)) == 1)

    Guess what? In this lesson we’ll be doing more practice with binary trees! And recursion! What could be more fun?

    Warm Up Debugging Challenge
    Warm Up Debugging Challenge

    Let’s warm up with another debugging challenge!

    Tree Depth
    Tree Depth

    As a warm up let’s write a recursive function to determine the depth or height of a tree. As a reminder, the depth is defined as the distance from the root node to the farthest leaf node. (The depth is not defined for a empty tree, since it has no root.)

    // Tree Depth

    Tree Node Count
    Tree Node Count

    Next, let’s look at an example of a recursive function that passes another data structure around. We’ll write a recursive method that returns an array with counts of the number of nodes that have zero, one, or two children. This will also prepare you for this lesson’s homework problem—which is a tricky one!

    // Tree Child Count

    Binary Search Tree
    Binary Search Tree

    Finally, let’s look again at the problem of locating a node in a binary tree. We’ll start with code from our previous answer, redesign it to be more efficient, and then analyze the performance of our new approach.

    import kotlin.random.Random
    class BinaryTree<T>(
    var value: T,
    var left: BinaryTree<T>? = null,
    var right: BinaryTree<T>? = null
    ) {
    constructor(values: List<T>) : this(values[0])
    private fun add(newValue: T) {
    if (Random.nextBoolean()) {
    if (right == null) {
    right = BinaryTree(newValue)
    } else {
    right!!.add(newValue)
    }
    } else {
    if (left == null) {
    left = BinaryTree(newValue)
    } else {
    left!!.add(newValue)
    }
    }
    }

    Solve: Binary Tree Search Path (Practice)

    Created By: Geoffrey Challen
    / Version: 2020.11.0

    Let's continue exploring recursion on binary trees. However, this problem takes a significant step forward in difficulty, so be prepared!

    We've provided a method pathToValue that accepts a BinaryTree<Any> as its first parameter and an Any as its second. It returns a List<Any> containing all the values in the tree on the way to the first node with a value equal to the passed Any, or null if the tree does not contain the passed Any. We've handled this case already for you in the starter code.

    Our wrapper method initializes the list properly and then calls a private helper method which performs the recursion. The helper should return true if the tree contains the value, and if it does also manipulate the list properly. If the tree does not contain the value it should return false. You will want to use add(int index, Any value) to add values to the front of the list as you work your way through the tree.

    This problem is hard! Here's an outline of a solution to help get you started:

    • If you reach an empty tree, you can return false, since an empty tree does not contain the value
    • Otherwise, if this node contains the value, add yourself to the list, stop recursing, and return true.
    • Otherwise, first search your right subtree. If that succeeds, then this node is also part of the path and should be added. If not, try the left subtree.
    • If neither the right nor left subtree contains the node, you should return false and not modify the list, since this node is not on the path to the desired node.

    Good luck and have fun!

    import cs125.trees.BinaryTree
    fun pathToValue(
    tree: BinaryTree<Any>,
    value: Any,
    ): List<Any>? {
    val path = mutableListOf<Any>()
    return if (pathToValue(tree, value, path)) {
    path
    } else {
    null
    }
    }
    private fun pathToValue(
    tree: BinaryTree<Any>?,
    value: Any,
    path: MutableList<Any>,
    ): Boolean {
    return false
    }

    Solve: BinaryTree to Map

    Created By: Geoffrey Challen
    / Version: 2021.4.0

    Create a method toMap that accepts a BinaryTree<*> and returns a Map<Any, Int> mapping the values in the tree to the count of the times that the value appears.

    Our suggestion is to have toMap create the map and then call a private recursive helper method to populate it. You will need to import cs125.trees.BinaryTree. We've provided some code to get you started.

    For reference, cs125.trees.BinaryTree is defined like this:

    Note that you may need to cast tree.value to Any so that you can add it to your map.

    import cs125.trees.BinaryTree
    fun toMap(tree: BinaryTree<*>): Map<Any, Int>? {
    // Create your map
    // Call the helper method to populate the map
    // Return the map
    return null
    }
    // Helper method
    private fun toMap(
    tree: BinaryTree<*>?,
    values: MutableMap<Any, Int>,
    ) {
    // Add to mutableMap<Any, Int> by casting to Any
    }

    More Practice

    Need more practice? Head over to the practice page.