James Lalonde
James Lalonde

Reputation: 79

Beginner Scheme: Turning Binary Search Trees into lists

I am having trouble with binary search trees and turning them into lists.

(define-struct node (key val left right))
;; A binary search tree (bst) is either
;; empty, or
;; a structure (make-node k v l r), where
;; k is a number (the key),
;; v is a string (the value),
;; l is a bst, where every key in l is less than k, and
;; r is a bst, where every key in r is greater than k.

Can anybody give me hints on how to approach this question?

Create a function bst that consumes a binary search tree and returns a list of all the strings in the value field of the binary search tree nodes and the list must be in descending order based on the key values in the binary search tree.

;;Examples: (bst (make-node 4 "James" (make-node 2 "Kien" empty empty)
;;(make-node 5 "Jack" empty (make-node 11 "Cole" empty empty)))) => (list "Cole" "Jack" "James" "Kien")

Thanks!

Upvotes: 1

Views: 9224

Answers (2)

Dota2
Dota2

Reputation: 474

(define (tree->list tree)
  (if(leaf? tree)
     (list (node tree))
     (cond((right-branch-only? tree)(append (list(node tree))
                                            (tree->list (right-branch tree))))
          ((left-branch-only? tree)(append (list(node tree))
                                           (tree->list (left-branch tree))))
          (else(append (list (node tree))
                       (append (tree->list (left-branch tree))
                               (tree->list (right-branch tree))))))))

Upvotes: 0

Óscar López
Óscar López

Reputation: 236004

Basically, you have to visit all the nodes in the tree using a reverse in-orden traversal (right subtree / value / left subtree), while at the same time creating a list with the answer. Something along these lines:

(define (tree->list tree)
  (if (empty? tree)
      empty
      (append (tree->list (node-right tree))
              (cons (node-val tree)
                    (tree->list (node-left tree))))))

It works as expected:

(define bst
  (make-node 4 "James"
             (make-node 2 "Kien" empty empty)
             (make-node 5 "Jack" empty
                        (make-node 11 "Cole" empty empty))))

(tree->list bst)
=> (list "Cole" "Jack" "James" "Kien")

Upvotes: 2

Related Questions