In SML:

Helpful functions:

Tree type:

datatype 'a Tree = LEAF of 'a | NODE of 'a * ('a Tree) * ('a Tree);

Returns tree as a post order list:

fun depthScan (LEAF n) = [n] | depthScan (NODE(n, L1, L2)) = depthScan(L1)@depthScan(L2)@[n];

Example:

datatype 'a Tree = LEAF of 'a | NODE of 'a * ('a Tree) * ('a Tree);

depthScan (NODE(1, NODE (2, NODE(3, LEAF 4 ,LEAF 5),LEAF 6), NODE(7,LEAF 8,LEAF 9)));

Output:

[4,5,3,6,2,8,9,7,1]

(b) depthSearch- 15% Write a function depthSearch takes a tree of type 'a Tree and an 'a value and returns the level of the tree where the value is found. If the value doesn't exist in the tree, it returns ~1. The tree nodes should be visited with depth-first post-order traversal and the level of the first matching node should be returned. The type of the depthSearch function should be: ''a Tree -'a -> int Level 1 2 1 Level 2 Level 3 2 5 Level 4 >val myTNODE (1, NODE (2, NODE (3, LEAF 2 ,LEAF 5), LEAF 1), NODE (1, LEAF 8, LEAF 5)) > depthSearch myT 1 > depthSearch myT 5 > depthSearch myT 8 >depthSearch myT 4 (b) depthSearch- 15% Write a function depthSearch takes a tree of type 'a Tree and an 'a value and returns the level of the tree where the value is found. If the value doesn't exist in the tree, it returns ~1. The tree nodes should be visited with depth-first post-order traversal and the level of the first matching node should be returned. The type of the depthSearch function should be: ''a Tree -'a -> int Level 1 2 1 Level 2 Level 3 2 5 Level 4 >val myTNODE (1, NODE (2, NODE (3, LEAF 2 ,LEAF 5), LEAF 1), NODE (1, LEAF 8, LEAF 5)) > depthSearch myT 1 > depthSearch myT 5 > depthSearch myT 8 >depthSearch myT 4