trees(cs)

Complete

Summary

Tree of numbers

js
const tree = list(list(1,2), 3, list(4));

// Box notation: [1, [2, null](#), [3, [[4, null], null]]]
tree1234

Concept

A tree of data type T is either:

  • null
  • or a pair,
    • whose tail is a tree of type T
    • and whose head is type T or a tree of type T

Every tree is a list, made up only of data type T and null

Application

Tree processing functions
Main idea:

  • if tree/list is empty return base case
  • if not empty, process the head and tail of the tree
js
function count_data_items(tree) {
	return is_null(tree)            
		   ? 0            
		   : (is_list(head(tree))               
			   ? count_data_items(head(tree))                
			   : 1 ) +
			 count_data_items(tail(tree));
}

function map_tree(f, tree) {     
	return map(sub_tree => !is_list(sub_tree) // check if not a list
						   ? f(sub_tree)      // if it is a number, apply the function              
						   : map_tree(f, sub_tree), // apply map_tree on the head as well
			   tree);
}