---
marp: true
title: 20 April 2021
theme: default
paginate: true
---
# CS 199 EMP
### Hosted by Jackie Chan and Akhila Ashokan
**Topics:** [Trees and Recursion](https://cs199emp.netlify.app/dist/s21/2021-04-20.html)
---
# Resources
Write code on the homepage or any playground on the site!
https://cs125.cs.illinois.edu/
Slides are on the course site!
https://cs199emp.netlify.app/
---
# What are Trees? What do we use them for?
A technical definition: a collection of entities called nodes. Nodes are connected by edges and each node has a value and possible a child note.
Real life examples: a company hierarchy, HTML document object model, a family tree
![Trees_Company](../../pics/trees_company.jpeg)
---
# Tree Terms
- root: fist node in the tree; usually at the top
- parent node: any node that has an edge pointing to another node
- child node: any node that has a parent node
- leaf node (leaves): any node that does not a child node
- height/depth of a tree: the distance from root node to farthest leaf node
---
# A Special Type of Tree: Binary Tree
---
![bg 70%](../../pics/trees_binary.jpeg)
---
# Combining Trees and Recursion
Trees and recursion go together. Why? Because trees are defined recursively. It's much easier to solve tree problems with recursion in play.
---
# Okay, enough talk. Let's do some practice problems!
---
# Find the Height of Binary Tree (10 mins)
Write a function to find the height of a binary tree. Use recursion!
```java
public class Node {
int val;
Node left;
Node right;
Node() { }
Node(int setVal) {
this.val = setVal;
}
Node(int setVal, Node setLeft, Node setRight) {
this.val = setVal;
this.left = left;
this.right = right;
}
}
public static int findHeight(Node root) {
// Write your code here.
}
```
---
# Find the Sum of Left Leaves (10 mins)
Write a function finds the sum of the left leaves given the root of the tree.
```java
public class Node {
int val;
Node left;
Node right;
Node() { }
Node(int setVal) {
this.val = setVal;
}
Node(int setVal, Node setLeft, Node setRight) {
this.val = setVal;
this.left = left;
this.right = right;
}
}
public int sumOfLeftLeaves(Node root) {
// write your code here
}
```
---
# Find a Value in a Binary Search Tree (10 mins)
Binary search trees are a special type of binary trees where the value in each node
- is greater than any value stored in the left sub-tree,
- and less than any value stored in the right sub-tree.
Write a function to find a value in the given binary search tree.
---
# Starter Code
```java
public class Node {
int val;
Node left;
Node right;
Node() { }
Node(int setVal) {
this.val = setVal;
}
Node(int setVal, Node setLeft, Node setRight) {
this.val = setVal;
this.left = left;
this.right = right;
}
}
public Node searchBST(Node root, int val) {
// write your code here
}
```
---
# That's all, folks!
Thanks for stopping by today. We hope you learned alot about how useful recursion is to solve tree problems.
Only a few more weeks to go! Hang in there everyone and enjoy the rest of your week.
---
# Solution Section
---
# Find the Height of Binary Tree - Solution
```java
public static int findHeight(Node root) {
if (root == null) {
return 0;
}
int lHeight = findHeight(root.left);
int rHeight = findHeight(root.right);
if (lHeight > rHeight) {
return lHeight + 1;
} else {
return rHeight + 1;
}
}
```
---
# Find the Sum of Left Leaves - Solution
```java
public int sumOfLeftLeaves(Node root) {
if (root == null) {
return 0;
}
return processSubtree(root, false);
}
private int processSubtree(Node subtree, boolean isLeft) {
// Base case: This is a leaf node.
if (subtree.left == null && subtree.right == null) {
if (isLeft) {
return subtree.val;
} else {
return 0;
}
}
// Recursive case: We need to add and return the results of the
// left and right subtrees.
int total = 0;
if (subtree.left != null) {
total += processSubtree(subtree.left, true);
}
if (subtree.right != null) {
total += processSubtree(subtree.right, false);
}
return total;
}
```
---
# Find A Value in a Binary Search Tree - Solution
```java
public Node searchBST(Node root, int val) {
if (root == null || val == root.val) {
return root;
}
if (val < root.val) {
return searchBST(root.left, val);
} else {
return searchBST(root.right, val);
}
}
```