Find the k-th child of a node in a tree. Use OCaml

Question

N/A · Accepted Answer

It depends on how you traverse tho...DFS and BFS will have a different k-th child of a node.

Anonymous · Answer

I think it means the k-th child according to an in-order traversal.  This code seems to work:

type 'a tree = | Node of 'a * 'a tree * 'a tree | Leaf

type 'a search = | KeepLooking of int | Found of 'a
let kthchild tree k =
  let rec aux t p =
    match t with
    | Leaf -> KeepLooking p
    | Node (v, l, r) ->
        begin match aux l p with
        | KeepLooking q ->
            if q = k then Found v
            else aux r (q+1)
        | Found w -> Found w end in
  match aux tree 1 with
  | Found v -> v
  | KeepLooking _ -> raise Not_found

Jane Street

Pergunta de entrevista da empresa Jane Street

Respostas da entrevista

Empresas seguidas

Buscas de vagas