CODEWITHSUNDEEP
treeschemeracket
virtuallyalike
virtuallyalike

Reputation: 5

SCHEME Preorder/Postorder/Inorder Traversal of a binary search tree

Trying to traverse a tree in scheme and I keep getting an error when I try to actually call/run the function.

(define (make-tree value left right)
  (list left value right))

(define (root tree)
  (car tree))

(define (left tree)
  (car (cdr tree)))

(define (right tree)
  (car (cdr (cdr tree))))

(define (preorder tree)
  (if (null? tree)
      '()
      (append (list (root tree))
              (preorder (left tree))
              (preorder (right tree)))))

(define (inorder tree)
  (if (null? tree)
      '()
      (append (inorder (left tree))
              (list (root tree))
              (inorder (right tree)))))


(define (postorder tree)  
  (if (null? tree)
      '()
      (append (postorder (left tree))
              (postorder (right tree))
              (list (root tree)))))

When I call the functions I get a car or cdr contradiction error. What's the proper way to execute these functions?

Upvotes: 0

Views: 185

Answers (1)

Martin Půda
Martin Půda

Reputation: 7568

Function make-tree and accessors root-left-right don't match: when you create tree with make-tree, root value will be in the middle, but your root function accesses car of the list.

So, rewrite make-tree like this:

(define (make-tree value left right)
  (list value left right))

See also this question for example tree and example of call and result.

Upvotes: 1

Related Questions