Kotlinlearncs.online LogoJava

    ← Prev

    Index

    Next →

    Kotlin
    Java

    • 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

    Trees and Recursion

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

    Next we’ll continue practicing with trees and recursion! And what better way to do that then to do a few problems together? So let’s get started!

    Count Left Greater Than Right
    Count Left Greater Than Right

    As a warm up, let’s do another counting problem. Given a binary tree containing Integers, let’s count the number of nodes where the value of the left child is greater than the value of the right child.

    Before we start, remember the core of our approach to recursion:

    // Binary Tree Count Left Greater Than Right

    Tree Search
    Tree Search

    Next, we’ll look at how to determine if a binary tree contains a certain value. This problem introduces a new wrinkle to our usual approach to recursion!

    // Binary Tree Search

    Solve: Binary Tree Count Equal to Child (Practice)

    Created By: Geoffrey Challen
    / Version: 2020.11.0

    Create a method named countEqualToEitherChild that accepts a single BinaryTree<*>? and counts the number of nodes in the tree where the value at that node is equal to either the value at its right child or the value at its left child. Keep in mind that not every node has a right or left child, so you'll need to check for null carefully. (Or use try-catch!) However, you can assume that all of the values in the tree are non-null.

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

    Algorithm Analysis
    Algorithm Analysis

    Next, let’s examine the performance of our recursive algorithms, and determine what O(n) category they belong in.

    // Binary Tree Algorithm Analysis

    Solve: BinaryTree Count Equal Children

    Created By: Geoffrey Challen
    / Version: 2021.10.0

    Create a method named countEqualChildren that accepts a single BinaryTree<*>? and counts the number of nodes in the tree that have two children with the same value. Keep in mind that not every node has a right or left child, so you'll need to check for null carefully. (Or use try-catch!) However, you can assume that all of the values in the tree are non-null.

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

    More Practice

    Need more practice? Head over to the practice page.