CODEWITHSUNDEEP
randomtreeschemebinary-tree
user2133623
user2133623

Reputation:

Walk randomly through a binary tree?

I'm making a program that takes a tree and randomly picks a branch (left or right) and returns those values in a list. For some reason it's not working. Any help?

Example:

~(rand-walk (tree 1 (leaf 2) (leaf 3)))
(1 2)

This is what I have so far:

(define (rand-walk tr)
 (if (empty-tree? tr) '()
   (if (leaf? tr) tr
      (if (equal? (random 1) 0)
              (cons ((root-value tr)(root-value (left-subtree tr))) '())
              (cons ((root-value tr)(root-value (right-subtree tr))) '())))))

Upvotes: 1

Views: 303

Answers (3)

GoZoner
GoZoner

Reputation: 70195

You got a number of problems in your code. Here is a proper implementation:

(define (rand-walk tr)
 (cond ((empty-tree? tr) '())
       ((leaf? tr) (list (root-value tr)))
       ((equal? (random 1) 0)
        (cons (root-value tr) (rand-walk (left-subtree tr))))
       (else
        (cons (root-value tr) (rand-walk (right-subtree tr))))))

If I was writing this I would use a tail recursive approach as:

(define (rand-walk tr)
  (assert (not (empty-tree? tr)))
  (let walking ((l '()) (tr tr))
    (let ((value (root-value tr)))
      (if (leaf? tr)
          (reverse (cons value l))
          (walking (cons value l))
                   ((if (zero? (random 1)) left-subtree right-subtree) tr))))))

Upvotes: 1

DWilches
DWilches

Reputation: 23035

If you want to traverse it then you should return a list when you reach a leaf:

(if (leaf? tr) (cons tr '())

And in you recursive steps you should cons with some recursive call:

(cons (root-value tr) (rand-walk (left-subtree tr)))

Upvotes: 1

paddy
paddy

Reputation: 63481

Disclaimer: I have never written in Scheme, but I had a brief encounter with LISP about 15 years ago =)

Your recursive part isn't recursive. You should be calling rand-walk on the subtree and consing that.

          (cons ((root-value tr)(rand-walk (left-subtree tr))) '())
          (cons ((root-value tr)(rand-walk (right-subtree tr))) '())))))

Upvotes: 1

Related Questions