Kth smallest element in a BST(scheme)

Question

Please disregard my broken English as i’m not a native speaker. I’m looking for the best way to find the kth smallest element in a BST, I’ve thought of ways like appending the tree to a list and traverse that list, but that takes too much time O(n) I’ve also considered deleting elements from the tree then find the smallest but that also takes more time. What is the best algorithm to approach this problem? As scheme is a functional programming language, the solution must be recursive. I’ve tried to look for an answer but most of the answers in C or Java would use some kind of an iterative format. Thank you for your help, My function should look like (Define (kth-smallest T k) ...)

To do this in better than O(*n*) it needs to be a balanced tree, and you need to be able to compute the size of a subtree without search. You haven't shown any code, so I have no idea if it's possible using your data structure or not. — kaya3, Nov 05 '19 at 21:53
My data structure is very simple. Define a tree as a list of a value, left and right. I saw your idea but I didn’t know how to implement it. But I guess it’s the right approach — CSE_Husky, Nov 05 '19 at 22:01

Sylwester · Answer 1 · 2019-11-06T01:20:36.730

If the BST is ordered and balanced, such that the leaf not most left is the lowest value. Then the nth lowest value would be the nth value you iterate over in an in order tree traversal.

So finding the lowest kth value in a balanced tree is between O(log n) and O(2n). O(n) it is then.

My implementation would create a helper that takes a continuation as well as k and the tree. The default continuation can be (lambda (v) #f) and thus if you want the 30th smallest in a 10 node tree it will call that and you get #f back. The second you find the deepest node and it's k is zero instead of calling the continuation it evaluates to the value of the current node.

If you were to delete the lowest value k times you'd have O(k * log n) ~ O(n log n) > O(n)

Good luck

score 0 · Answer 2 · answered Nov 06 '19 at 07:05

If the size of the left subtree is larger than k, we look in the left sub-tree, if it is smaller we look at the right subtree with the new k: k - size-of-left-subtree - 1, otherwise (in the equal case) we return the value at the current node. This is performed in O(lg n) time.

#lang racket

(struct no-info ())
(define NONE (no-info))

; [BST X] is one of:
; - (node NONE NONE NONE 0)
; - (node BST  BST  X    Number)

(struct node [left right val size])
(define leaf (node NONE NONE NONE 0))

; examples
(define lt (node (node (node leaf leaf 10 1) (node leaf leaf 24 1) 15 3) leaf 29 4))
(define rt (node (node leaf leaf 77 1) (node leaf (node leaf leaf 99 1) 95 2) 89 4))
(define t (node lt rt 63 9))

;           63
;          /  \
;        29    89
;       /     /  \
;      15    77  95
;    /   \         \ 
;  10     24       99

; node val: 10 15 24 29 63 77 89 95 99
; rank:     1  2  3  4  5  6  7  8  9

; kth-smallest : BST -> X
; the value of the `k`th smallest node in `t`
(define (kth-smallest t k)
  (define (kth-smallest-h t k)
    (cond [(equal? (node-size t) 1) (node-val t)]
          [else (let ([s (node-size (node-left t))])
                  (cond [(> s k) (kth-smallest-h (node-left t) k)]
                        [(< s k) (kth-smallest-h (node-right t) (sub1 (- k s)))]
                        [else (node-val t)]))]))
  (if (or (<= k 0) (> k (node-size t)))
      (error "k out of range")
      (kth-smallest-h t (sub1 k))))


(map (λ (x) (kth-smallest t x)) '(1 2 3 4 5 6 7 8 9))
; => '(10 15 24 29 63 77 89 95 99)

Kth smallest element in a BST(scheme)

2 Answers2