Найти самый длинный лист слева для каждого узла в двоичном дереве - разрешено - обход дерева в OCaml - левые листья

Question

Мне удалось выполнить эту задачу. Ответ ниже. Возможно, кому-то понадобится это решение.

У вас есть двоичное дерево в OCaml. У каждого узла есть int, левый ребенок, правый ребенок и ссылка на узел.

type tree = Node of tree * int * tree * tree ref | Leaf;; 

процедура запись left_leaves : tree -> unit эта процедура должна установить ссылку на каждом узле с глубочайшим левым ребенком.

  25 
    / \ 
    5  30 
/\ 
    4 10 
//
2 6 

для каждого узла эта процедура должна установить ссылку на этот узел, как, что:

25 -> Node(Leaf, 2, Leaf, Leaf) 
5 -> Node(Leaf, 2, Leaf, Leaf) 
4 -> Node(Leaf, 2, Leaf, Leaf) 
2 -> Leaf 
10 -> Node(Leaf, 6, Leaf, Leaf) 
6 -> Leaf 
30 -> Leaf 

Как написать эту процедуру в OCaml? Я думал о рекурсии. Мы должны идти со дна дерева. Сначала мы должны изменить ссылку на лист. Затем в следующем шаге мы должны изменить ссылку на левый узел, а затем рекурсивно изменить каждую ссылку в узле на ссылку своего левого дочернего элемента. Я сделал процедуру добавления, которая строит деревья BST для целей тестирования:

let rec add x tree = 
match tree with 
|Node (l, k, r, wsk) -> 
if x <= k then 
Node (add x l, k, r, wsk) 
else 
Node(l, k, add x r, wsk) 
|Leaf -> Node (Leaf, x, Leaf, ref Leaf) 

let a = Node (Leaf, 25, Leaf, ref Leaf);; 

let a = add 5 a;; 

let a = add 10 a;; 

let a = add 4 a;; 

let a = add 2 a;; 

let a = add 10 a;; 

let a = add 30 a;; 

let a = add 26 a;; 

Это мое решение, но оно не работает. Понятия не имею почему.

Редактировать: во время издания этого сообщения я понял, как это сделать. Мой код:

let rec left_leaves tree = 
match tree with 
|Node (l, k, r, wsk) -> 
(match l with 
|Node (ll, lk, lr, lwsk) -> 
left_leaves l; if ll = Leaf then wsk := l else wsk := !lwsk; left_leaves r; 
|Leaf -> wsk := Leaf 
) 
|Leaf ->();; 

Answer 1

Мое решение в порядке. Во время издания этого сообщения мне удалось это сделать. ; D