Recursive data: trees

A tree is a recursive type

A data declaration may refer to the type it declares. That one sentence is enough for lists, trees and every structure with a nested shape: data Tree = Leaf | Node Tree Int Tree is a leaf or a value with a left subtree and a right subtree. The definition is finite and the values can be arbitrarily deep.

data Tree = Leaf | Node Tree Int Tree deriving (Show)

The type is a sum of a product: a choice between leaf and node, where the node holds two subtrees and a value. This is the binary search tree of the algorithms course, declared in two lines, and the functions below are the operations that keep it ordered.

Insert into a search tree

The invariant is that everything in the left subtree is smaller than the node and everything in the right subtree is larger. Insert walks down comparing, rebuilds the nodes on the way back, and stops at a leaf. A duplicate value leaves the tree as it was.

insert :: Int -> Tree -> Tree insert x Leaf = Node Leaf x Leaf insert x tree@(Node left value right) | x < value = Node (insert x left) value right | x > value = Node left value (insert x right) | otherwise = tree fromList :: [Int] -> Tree fromList = foldr insert Leaf

The tree@(Node ...) is the as-pattern of the lesson on pattern matching: it names the whole node so the duplicate case can return it unchanged. fromList is a fold, because inserting a list into a tree is the same shape as summing a list.

module Main (main) where data Tree = Leaf | Node Tree Int Tree deriving (Show) insert :: Int -> Tree -> Tree insert x Leaf = Node Leaf x Leaf insert x tree@(Node left value right) | x < value = Node (insert x left) value right | x > value = Node left value (insert x right) | otherwise = tree fromList :: [Int] -> Tree fromList = foldr insert Leaf toList :: Tree -> [Int] toList Leaf = [] toList (Node left value right) = toList left ++ [value] ++ toList right main :: IO () main = do let tree = fromList [5, 3, 8, 1, 4] print tree print (toList tree)

ghc -Wall -O1 -o tree tree.hs
./tree

Node (Node Leaf 1 (Node Leaf 3 Leaf)) 4 (Node (Node Leaf 5 Leaf) 8 Leaf)
[1,3,4,5,8]

The shape is not the one a drawing would suggest, because foldr inserts the last element first: 4 becomes the root, then 1, 8, 3 and 5 are placed around it. The in-order traversal is sorted regardless, which is the property that makes the structure useful.

Walking it in order

toList visits the left subtree, then the value, then the right subtree. On a search tree that order is sorted, and the proof is the invariant of the insert: everything smaller is on the left, everything larger on the right, so the concatenation of the three parts is in order.

toList Leaf = [] toList (Node left value right) = toList left ++ [value] ++ toList right

The concatenation is simple and, on a large tree, wasteful: each node copies the list of its left subtree. The usual fix is an accumulator, or the difference-list trick, and the lesson on Foldable shows the same traversal written as a fold that builds the list once.

A fold over the tree

Recursion over a tree follows the type: one case for the leaf, one for the node, and two recursive calls in the node case. A sum and a depth are the two smallest examples, and they show the shape that a general fold later captures.

module Main (main) where data Tree = Leaf | Node Tree Int Tree deriving (Show) leafSum :: Tree -> Int leafSum Leaf = 0 leafSum (Node left value right) = leafSum left + value + leafSum right depth :: Tree -> Int depth Leaf = 0 depth (Node left _ right) = 1 + max (depth left) (depth right) main :: IO () main = do let tree = Node (Node Leaf 1 Leaf) 3 (Node Leaf 5 Leaf) print (leafSum tree) print (depth tree)

ghc -Wall -O1 -o tree_fold tree_fold.hs
./tree_fold

9
2

The sum visits every node and adds the values; the depth asks both subtrees and keeps the larger answer. The second argument of the node pattern is _ because the value itself does not matter for the depth, which is the wildcard doing its job. A balanced tree of a thousand nodes is ten levels deep, and that number is the cost of a lookup.

Exercises

  1. Write member :: Int -> Tree -> Bool and use the ordering to visit one side only.
  2. Write minimumTree :: Tree -> Maybe Int by walking left until a leaf.
  3. Count the nodes with a recursive function, then with length . toList.
  4. Insert the same five numbers in sorted order and compare the depth with the tree of the lesson.
  5. Write mapTree :: (Int -> Int) -> Tree -> Tree.
  6. Explain why toList of a search tree is sorted.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What does data Tree = Leaf | Node Tree Int Tree describe?

    Answer

    A leaf or a node holding a left subtree, a value and a right subtree

    The declaration is recursive: a node contains two more trees and one value.

  2. What does insert x Leaf return?

    Answer

    Node Leaf x Leaf

    The base case places the value in a new node with two empty subtrees.

  3. Which traversal of a search tree produces a sorted list?

    Answer

    Left subtree, then value, then right subtree

    The invariant puts smaller values on the left and larger on the right, so in-order is ascending.

  4. What does this program print? module Main (main) where data Tree = Leaf | Node Tree Int Tree deriving (Show) main :: IO () main = print (Node (Node Leaf 1 Leaf) 3 (Node Leaf 5 Leaf))

    Answer

    Node (Node Leaf 1 Leaf) 3 (Node Leaf 5 Leaf)

    The derived Show prints the tree structurally, with every constructor and value.

  5. What does the duplicate case of insert do?

    Answer

    Returns the tree unchanged

    The as-pattern names the whole node, and the otherwise guard returns it as it was.

  6. What does leafSum (Node Leaf 3 (Node Leaf 5 Leaf)) return?

    Answer

    8

    The sum adds 3 and 5 with the empty left subtree.

  7. What is the depth of a tree with one node?

    Answer

    1

    The node case adds one to the depth of its subtrees, and a leaf has depth zero.

  8. What does this program print? module Main (main) where data Tree = Leaf | Node Tree Int Tree deriving (Show) depth :: Tree -> Int depth Leaf = 0 depth (Node left _ right) = 1 + max (depth left) (depth right) main :: IO () main = print (depth (Node (Node Leaf 1 Leaf) 3 (Node Leaf 5 Leaf)))

    Answer

    2

    Both subtrees are one level deep, so the root adds one and the answer is 2.

  9. What is the cost of toList (Node left value right) written with ++?

    Answer

    It copies the left list at every node, so it can be quadratic

    ++ walks its left argument, and at each node that argument is the whole left traversal, which is copied again.

  10. Why is the root of fromList [5, 3, 8, 1, 4] the value 4?

    Answer

    foldr inserts the last element first, and it becomes the root

    foldr starts from the right end of the list, so 4 is inserted into an empty tree first.

The code on this page was built with GHC 9.10.3 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev