I am working on a program that is supposed to build a tree using nested lists in Racket. I believe I am very close, but I am stuck on one section of my insertion testing process.
The syntax for my tree looks like this:
- Numbers that are less than or equal to the root must go to the left
- Numbers that are greater must go to the right
- An empty right child does not need to be represented
- An empty left child must be represented with a '()
Empty tree -> '()
1 root node '(8)
left child (less than) ((8) (3))
right child (greater than ((8) (() 12))
root with a left and right child ((8) (3 12))
Root's Right child has nodes ((8) (3 ((12) (10)))) | 10 is greater than 8 -right> but less than 12 -left>
Root's Left Child has nodes '((8) ((3) (3)) 12) | 3 is less than 8 -left> and less than or equal to 3 -left>
Root's Right child with missing left node ((8) (3 ((12) ('() 13)))) | 13 is greater than 8 -right> and greater than 12 -right> a missing left child is represented with '()
Root's Left child with missing left node ((8) (3 (() 4)) 12) | 4 is less than 8 -left> but is greater than 3 -right>
So far, I have this recursive tree-insert function that works well save for a test case like this:(tree-insert 3 '((8) ((3) (3)) ((12) (10)))) and like this:(tree-insert 3 '((8) ((3) (3))))
(define (tree-insert num tree)
(cond
[(equal? tree '()); if the tree we are trying to insert into is empty ;CASE 1
(list num)] ;just return the tree with the number inserted
[(equal? (cdr tree) '()) ; CASE 2
(if (> num (car tree))
(list (car tree) (list '() num))
(list (list (car tree)) (list num))
)
]
;at this point we have only confirmed that there IS a child, but we do not know which
[(and (> num (caar tree)) (equal? (cdadr tree) '()) );has only a left child and number to insert is greater
(list (car tree) (list (caadr tree) num)) ;CASE 3
]
[(and (<= num (caar tree)) (equal? (caadr tree) '()) ) ;has only a right child and number to insert is less
(list (car tree) (list num (cadadr tree))) ;CASE 4
]
[(and (<= num (caar tree)) (equal? '() (cdadr tree))) ;has only a left child and number to insert is less
(list (car tree) (tree-insert num (list(caadr tree)))) ;CASE 5
] ;(list (cadadr tree))
[(and (> num (caar tree)) (equal? '() (caadr tree)));has only a right child and number to insert is greater
(list (car tree) (list (caadr tree) (tree-insert num (list (cadadr tree))))) ;CASE 6
]
;; ;at THIS point we have confirmed that there are at least children in both sections
[(<= num (caar tree)); if the value is less than root and there are 2 children
(list (car tree) (tree-insert num (list (caadr tree))) (cadadr tree))] ;CASE 7
;;
[(> num (caar tree)) ;if the value is greater than root and there are 2 children
(list (car tree) (list(caadr tree) (tree-insert num (list (cadadr tree)))))];CASE 8
)
)
In my tests, I have this
(tree-insert 8 '())
(tree-insert 3 '(8))
(tree-insert 12 '((8) (3)))
(tree-insert 3 '((8) (() 12)))
(tree-insert 2 '((8) (3)))
(tree-insert 14 '((8) (() 12)))
(tree-insert 77 '((8) (3)))
(tree-insert 2 '((8) (3 12)))
(tree-insert 10 '((8) (3 12)))
(tree-insert 8 '((8) (3 12)))
(tree-insert 3 '((8) (3 ((12) (10)))))
(tree-insert 3 '((8) ((3) (3)) ((12) (10))));;ERROR
(tree-insert 3 '((8) ((3) (3))));;ERROR
The (tree-insert 3 '((8) ((3) (3)) ((12) (10)))) and (tree-insert 3 '((8) ((3) (3)))) are the test cases that are giving me the error.
My outputs for the tests are
'(8)
'((8) (3))
'((8) (3 12))
'((8) (3 12))
'((8) ((3) (2)))
'((8) (() (12 (() 14))))
'((8) (3 77))
'((8) ((3) (2)) 12)
'((8) (3 ((12) (10))))
'((8) (3 (() 8)) 12)
'((8) ((3) (3)) ((12) (10)))
>: contract violation
expected: real?
given: '(3)
Ideally the output for the error test cases are:
(tree-insert 3 '((8) ((3) (3)) ((12) (10)))) - > ((8) ((3) ((3) (3))) ((12) (10)))
(tree-insert 3 '((8) ((3) (3)))) -> '((8) ((3) ((3) (3))))
I'm not sure if I am returning the recursively built lists correctly. Am I doing something wrong when rebuilding the lists?
Any help would be appreciated
'((8) (3 12))vs'((8) ((3) (2))). There looks like a lot of inconsistency over the structure, which is likely the cause of that error. Is this format something you have any control over?(> num (car tree)), but thecarof a tree may be a list in your code. With(tree-insert 3 '((8) ((3) (3))))->(tree-insert 3 '((3)))in CASE 7 the problem is triggered. In any case, the code seems convoluted and too complex for a binary tree implementation. I would rethink the tree design.elsefor the finalcondclause instead of yet another contitional?