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`#### 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`

import cs125.trees.BinaryTree;

int countLeftGreaterThanRight(BinaryTree tree) {

return 0;

}

assert countLeftGreaterThanRight(new BinaryTree<Integer>(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

As a warm up, let’s do another counting problem.
Given a binary tree containing `Integer`

s, 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:

- Identify the base case—the simplest problem that you have to be able to immediately solve
- Make the problem smaller at each step
- Combine results appropriately

// Binary Tree Count Left Greater Than Right

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

Created By: Geoffrey Challen

/ Version: `2020.11.0`

Create a public class `BinaryTreeCounter`

that provides a single class 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`

has the following public properties:

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

Created By: Geoffrey Challen

/ Version: `2021.10.0`

Create a public class `BinaryTreeCounter`

that provides a single class method named `countEqualChildren`

that
accepts a single `BinaryTree<?>`

and counts the number of nodes in the tree that have two children with equal
values.
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 the *values* in the tree are non-null.

For reference, `cs125.trees.BinaryTree`

has the following public properties:

Need more practice? Head over to the practice page.