# 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 RightCount 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 SearchTree 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 ## 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:

## Algorithm AnalysisAlgorithm Analysis

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

// Binary Tree Algorithm Analysis ## 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:

## More Practice

Need more practice? Head over to the practice page.