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

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

Interactive Walkthrough

Click on an icon below to start!

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!

Interactive Walkthrough

Click on an icon below to start!

## Practice: Binary Tree Count Equal to Child

Created By: learncs.online Staff

/ 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:

Please Log In to Complete Homework Problems

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

Interactive Walkthrough

Click on an icon below to start!

## Homework: BinaryTree Count Equal Children

Created By: learncs.online Staff

/ 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:

Please Log In to Complete Homework Problems

## More Practice

Need more practice? Head over to the practice page.