Practice Problems: Recursion with Trees (Pyret)

Tests are given for all practice problems (functions, not definitions) for you to run against your own implementation.

Problem Statement: Create a binary tree data structure and implement basic operations using recursion.

Part A: Define the Data Define a BinaryTree data type with two variants:

• leaf with field: value (Number)
• node with fields: value (Number), left (BinaryTree), right (BinaryTree)

Part B: Create Functions Write the following functions:

1. tree-size - count total number of nodes in the tree
2. tree-sum - add up all values in the tree
3. tree-height - find the maximum depth of the tree
4. tree-contains - check if a specific value exists in the tree

Template:

# Part A: Define the data
data BinaryTree:
  # write your data definition here
end

# Part B: Create functions
fun tree-size(tree :: BinaryTree) -> Number:
  # write your function here
where:
  tree-size(leaf(5)) is 1
  tree-size(node(10, leaf(5), leaf(15))) is 3
  tree-size(node(10, node(5, leaf(2), leaf(7)), leaf(15))) is 5
  tree-size(node(1, node(2, leaf(4), leaf(5)), node(3, leaf(6), leaf(7)))) is 7
end

fun tree-sum(tree :: BinaryTree) -> Number:
  # write your function here
where:
  tree-sum(leaf(5)) is 5
  tree-sum(node(10, leaf(5), leaf(15))) is 30
  tree-sum(node(10, node(5, leaf(2), leaf(7)), leaf(15))) is 39
  tree-sum(node(0, leaf(-5), leaf(5))) is 0
end

fun tree-height(tree :: BinaryTree) -> Number:
  # write your function here
where:
  tree-height(leaf(5)) is 1
  tree-height(node(10, leaf(5), leaf(15))) is 2
  tree-height(node(10, node(5, leaf(2), leaf(7)), leaf(15))) is 3
  tree-height(node(1, node(2, node(3, leaf(4), leaf(5)), leaf(6)), leaf(7))) is 4
end

fun tree-contains(tree :: BinaryTree, target :: Number) -> Boolean:
  # write your function here
where:
  tree-contains(leaf(5), 5) is true
  tree-contains(leaf(5), 10) is false
  tree-contains(node(10, leaf(5), leaf(15)), 15) is true
  tree-contains(node(10, leaf(5), leaf(15)), 20) is false
  tree-contains(node(10, node(5, leaf(2), leaf(7)), leaf(15)), 7) is true
  tree-contains(node(10, node(5, leaf(2), leaf(7)), leaf(15)), 12) is false
end