# Create A Program To Manipulate Binary Trees In Haskell Language Assignment Solution

July 08, 2024
Dr. Benjamin
🇦🇺 Australia
Dr. Mitchell holds a Ph.D. in Computer Science from the University of Oxford and has completed over 800 Haskell assignments with exceptional results. With a decade of experience in academia and industry, he specializes in advanced BYTESTRING algorithms, network programming, and memory management. Dr. Mitchell's expertise lies in optimizing BYTESTRING operations for performance and efficiency, making him a valuable asset for students seeking comprehensive assistance.
Key Topics
• Instructions
• Requirements and Specifications
Tip of the day
News

## Instructions

Objective

Write a haskell assignment program to Manipulate binary trees.

## Requirements and Specifications

Given a binary search tree t, bstInsert x t is a binary search tree formed by

-- replacing a Tip in t with (Bin x Tip Tip) or t, if t already contains x.

--

-- *HW2> bstInsert 3 bst1

-- Bin 2 (Bin 0 Tip Tip) (Bin 4 (Bin 3 Tip Tip) Tip)

-- *HW2> bstInsert 1 bst1

-- Bin 2 (Bin 0 Tip (Bin 1 Tip Tip)) (Bin 4 Tip Tip)

-- *HW2> bstInsert (-1) bst1

-- Bin 2 (Bin 0 (Bin (-1) Tip Tip) Tip) (Bin 4 Tip Tip)

-- *HW2> bstInsert 2 bst1

-- Bin 2 (Bin 0 Tip Tip) (Bin 4 Tip Tip)

--

-- Note: bstInsert should assume that the tree is a valid binary search tree, meaning

-- that the root is greater than all elements in its left subtree and less than all

-- elements in its right subtree. If bstInsert is given a binary search tree, its output

-- must also be a binary search tree. If bstInsert is given a tree that is not a binary

-- search tree, any convenient output is acceptable.

bstInsert :: Ord a => a -> Tree a -> Tree a

bstInsert = undefined

Screenshots of output

Source Code

```module HW2 where data List a = Nil | Cons a (List a) deriving (Show, Eq, Ord) data Tree a = Tip | Bin a (Tree a) (Tree a) deriving (Show, Eq, Ord) bst1 = Bin 2 (Bin 0 Tip Tip) (Bin 4 Tip Tip) bst2 = Bin 5 bst1 (Bin 7 (Bin 6 Tip Tip) Tip) -- 0. emptyTree t returns True if and only if its argument is Tip emptyTree :: Tree a -> Bool emptyTree Tip = True emptyTree _ = False -- As with HW1, replace each incorrect definition with a correct definition. For example, -- -- emptyTree Tip = True -- emptyTree _ = False -- 1. size t returns the total number of elements in t. This is the same as the number of -- Bin nodes in t. -- -- *HW2> size bst1 -- 3 -- *HW2> size bst2 -- 6 size :: Tree a -> Int size Tip = 0 size (Bin _ lt rt) = size lt + size rt + 1 -- 2. height t returns the height of t. This is the length of the longest path from the -- root node to a Tip. -- -- *HW2> height Tip -- 0 -- *HW2> height bst1 -- 2 -- *HW2> height bst2 -- 3 -- *HW2> height (Bin 19 bst2 Tip) -- 4 height :: Tree a -> Int height Tip = 0 height (Bin _ lt rt) = max (height lt) (height rt) + 1 -- 3. perfect n a returns a "perfect" binary tree of height n containing the value -- a for all nodes. In a perfect binary tree, all nodes have either two children -- or no children. -- -- *HW2> perfect 2 'a' -- Bin 'a' (Bin 'a' Tip Tip) (Bin 'a' Tip Tip) -- -- In general, we expect the following rules to hold: -- for all positive integers n and all arbitrary values x: -- height (perfect n x) == n -- size (perfect n x) == 2^n - 1 perfect :: Int -> a -> Tree a perfect 0 _ = Tip perfect 1 x = Bin x Tip Tip perfect n x = Bin x (perfect (n - 1) x) (perfect (n - 1) x) -- 4. inorder t returns a list containing all the elements of t in order, meaning the -- elements of the left subtree (in order), followed by the root, followed by the -- elements of the right subtree (in order). -- -- *HW2> inorder Tip -- [] -- *HW2> inorder bst1 -- [0,2,4] -- *HW2> inorder bst2 -- [0,2,4,5,6,7] -- *HW2> inorder (Bin 19 bst2 Tip) -- [0,2,4,5,6,7,19] -- *HW2> inorder (Bin 19 Tip bst2) -- [19,0,2,4,5,6,7] -- -- In general, for all binary trees t, we expect -- length (inorder t) == size t -- -- Note: the order in "inorder" is the order of items in the tree, not their sorted -- order. Your implementation should not perform any comparisons. inorder :: Tree a -> [a] inorder Tip = [] -- if tree, get inorder list from left, append to root element and then append -- to right inorder list inorder (Bin x lt rt) = inorder lt ++ [x] ++ inorder rt -- 5. Given a binary search tree t, bstInsert x t is a binary search tree formed by -- replacing a Tip in t with (Bin x Tip Tip) or t, if t already contains x. -- -- *HW2> bstInsert 3 bst1 -- Bin 2 (Bin 0 Tip Tip) (Bin 4 (Bin 3 Tip Tip) Tip) -- *HW2> bstInsert 1 bst1 -- Bin 2 (Bin 0 Tip (Bin 1 Tip Tip)) (Bin 4 Tip Tip) -- *HW2> bstInsert (-1) bst1 -- Bin 2 (Bin 0 (Bin (-1) Tip Tip) Tip) (Bin 4 Tip Tip) -- *HW2> bstInsert 2 bst1 -- Bin 2 (Bin 0 Tip Tip) (Bin 4 Tip Tip) -- -- Note: bstInsert should assume that the tree is a valid binary search tree, meaning -- that the root is greater than all elements in its left subtree and less than all -- elements in its right subtree. If bstInsert is given a binary search tree, its output -- must also be a binary search tree. If bstInsert is given a tree that is not a binary -- search tree, any convenient output is acceptable. bstInsert :: Ord a => a -> Tree a -> Tree a bstInsert x Tip = Bin x Tip Tip bstInsert x (Bin y lt rt) = -- if equal to the value, return the tree if x == y then (Bin x lt rt) -- if smaller than value in root, recurse to insert at left subtree else if x < y then Bin y (bstInsert x lt) rt -- else, it's greated than value in root, recurse to insert at right subtree else Bin y lt (bstInsert x rt) ```

## Related Samples

Check out our free Haskell assignment samples to enhance your understanding of this functional programming language. Our examples provide detailed solutions and insights, helping you grasp complex concepts and improve your skills effectively.