Trees and Recursion

Kotlin

Created By: Geoffrey Challen

/ Updated: 2022-05-23

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

• 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

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!

Algorithm Analysis

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

More Practice

Need more practice? Head over to the practice page.