CODEWITHSUNDEEP
lispschemebinary-search-tree
helloimbarbara
helloimbarbara

Reputation: 95

Searching through BST in Lisp

I'm writing a program that directs a robot down a BST to the goal number. The program has two input parameters, a destination as an integer, and a map that represents all the paths the robot can follow.

ie: (robot 64 '(53 ( () ( 64 () () ) ))) )

Where 64 is the destination and 53 ( () ( 64 () () ) )) is the BST.

I need help writing the method. Here is what I was originally working on. 

(define (robot goal map)
  (let ((x (car map)))
    (define empty? '())
    (display x)
    (cond (empty? x)
          (robot goal (cadr map)))
    (cond ((= goal x)) (display x))
    (cond (< x goal)
          (robot goal (cadr map)))
    (cond (> x goal)
          (robot goal (caddr map)))
    ;(display "NULL")
  ) 
)

It's supposed to search through the BST, and if the path is found it prints (found: # T # T ... # T #), if your destination is in the tree but not the root (# is a position number and T is either L or R indicating that you took a Left or Right turn at position #.

Note: I've never used Lisp until yesterday, so sorry if I seem a bit lost.

Upvotes: 1

Views: 319

Answers (1)

&#211;scar L&#243;pez
&#211;scar L&#243;pez

Reputation: 236004

The procedure's structure is incorrect for the problem at hand - you're not handling the recursion correctly, and you're not building a list along the way, for the requested output. Also that's not the correct way to use cond, and you should not redefine the existing procedures map and empty?. Also, what happens if the element is not in the tree? you can't do (car tree) until you're certain that the tree is non-empty.

I'll provide the correct structure of the solution and give you some hint so you can work out the solution by yourself, if the element was not found in the tree we'll return a list with the value not-found in the last position.

(define (robot goal tree)
  (cond ((empty? tree)     ; if the tree is empty
         '(not-found))     ; return special value indicating it
        ((= <???> goal)    ; if the current element is goal
         <???>)            ; return a list with current element
        ((< goal <???>)    ; if goal is less than current element
         (cons <???>       ; cons current element
               (cons <???> ; with L and advance the recursion
                     (robot goal <???>))))   ; going to the left
        (else              ; otherwise
         (cons <???>       ; cons current element
               (cons <???> ; with R and advance the recursion
                     (robot goal <???>)))))) ; going to the right

Notice that the correct way to search a BST will always be:

  1. Check if the tree is empty
  2. If not, check if the current element is the one we're looking for
  3. If not, check if the element we're looking for is less than the current element, and go to the left subtree if that's the case
  4. Otherwise go to the right subtree

As a final advice, don't forget to test your solution:

(robot 64 '(53 () (64 () ())))
=> '(53 R 64)

(robot 42 '(53 () (64 () ())))
=> '(53 L not-found)

Upvotes: 1

Related Questions