CODEWITHSUNDEEP
recursiontreeschemeracket
Ben
Ben

Reputation: 38

Scheme find far left node of a tree recursively

I am writing a function that finds the farthest left node in any tree. The function does not traverse the tree or give the farthest left node but just gives the left most child of the first node.

(define (far-left tree)
  (cond (null? (cadr tree))
        (car tree)
        (far-left (cdr tree))))

sample input, which gives many nodes rather than the desired one:

(display (far-left '(1 (3 4 (6 7 (12 13))) 8 9 (10 11))))

Upvotes: 0

Views: 538

Answers (2)

molbdnilo
molbdnilo

Reputation: 66371

What you call "the left most child of the first node" is (cadr tree).
There is one (cadr tree) in your function, and that suggests that the first condition is always true.
And that is what's happening.

cond's form is

(cond clause-1 clause-2 ...)

Each clause in turn has the form (condition value).

That is,

(cond (condition-1 value-1)
      (condition-2 value-2)
      (condition-3 value-3)
      ...)

If you match this to your function, you will see that

  • null? is condition-1 and (cadr tree) is value-1,
  • car is condition-2 and tree is value-2, and
  • far-left is condition-3 and (cdr tree) is value-3.

Since null? is not #f, the first clause is always selected.

The correct form is

(define (far-left tree)
    (cond
        ((null? (cadr tree)) (car tree))
        (else (far-left (cdr tree)))

This code still does not work, though.
Fixing the bugs left as an exercise.

Upvotes: 3

Atharva Shukla
Atharva Shukla

Reputation: 2137

Data Definition: Tree

  • A Tree is either a Leaf or a Node where:
    • A Leaf is a Number.
    • A Node is a non-empty list of sub-Trees .

Function: far-left

  • Condition 1: A Leaf as an input is invalid because we're supposed to find the "farthest left node in any tree.
  • Condition 2: If a Node has Leaf as its left-most (or first) element, then it is the left-most node. If the left-most element is a Tree that is not a Leaf we recur on it.
#lang typed/racket

(define-type Leaf Number)
(define-type Node (Pairof Tree (Listof Tree)))
(define-type Tree (U Leaf Node))

(: far-left (-> Tree Node))
(define (far-left tree)
  (cond [(number? tree) (error "Farthest left node of a leaf does not exist!")]
        [(cons? tree)   (if (number? (first tree)) tree (far-left (first tree)))]))

Tests:

(far-left '(1 (3 4 (6 7 (12 13))) 8 9 (10 11)))
; =>  '(1 (3 4 (6 7 (12 13))) 8 9 (10 11))

(far-left '((3 4 (6 7 (12 13))) 1  8 9 (10 11)))
; => '(3 4 (6 7 (12 13)))

(far-left '(((6 7 (12 13)) 3 4) 1  8 9 (10 11)))
; => '(6 7 (12 13))

(far-left '((((12 13) 6 7) 3 4) 1  8 9 (10 11)))
; => '(12 13)

Upvotes: 2

Related Questions