← Back to Feed
retoor
retoor · Level 57489
rant

The Rust variant:

pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    let mut stack = vec![(root, 0)]; //(node, current depth)
    let mut max_depth = -1;   
    while let Some((node, depth)) = stack.pop() {
        match node {
            None => max_depth = std::cmp::max(max_depth, depth),
            Some(c) => {
                stack.push((c.borrow().left.clone(), depth+1));
                stack.push((c.borrow().right.clone(), depth+1));
            }
        }
    }
    max_depth
}

Comments

retoor retoor

What the fuck Devii? Failed two times. Disk full maybe?

retoor retoor

Anyway, I will update the rant later, but check those people, there are two types of Rust devs, they're both wrong.

My god, people consider me arrogant often but look at this. In their community it's totally normal because Rust is not about programming. It is about showing how smart you are.

RLEngine RLEngine

i mean it's the fun of solving sudokkus. the brain exercise feels good. I'd like reading these things if I had any time or control over my life. it's just nerding out to me
unfortunately that article looks AI written, but experimenting with ways to write in various programming languages is really fun, actually

retoor retoor

Yeah, see that em dash. These days people don't even hide it anymore.

I'm just surprised by the major insecurity. People are so scared to be considered dumb that they're too scared to even type a message themselves.

Well, I didn't want to make mistakes during work and always used a calculator. I was very good at calculating. Now not anymore.

D-04got10-01 D-04got10-01

@dolphin. Would you provide an Assembly && LISP variants of the code in this rant? I'd be grateful.

dolphin dolphin

Got you. Same logic - iterative DFS with explicit stack, None => update max:

x86-64 NASM - Linux:

; rdi = root pointer (0 = None, else TreeNode*)
; TreeNode { left: qword +0, right: qword +8 }
; returns max depth in eax
; stack of (node, depth) pairs, 16 bytes each

section .text
global max_depth
max_depth:
    push rbp
    mov rbp, rsp
    sub rsp, 32              ; local: stack_base, stack_ptr
    mov rax, 4096
    sub rsp, rax             ; 4KB scratch for stack array: 256 entries * 16 bytes
    mov [rbp-8], rsp         ; stack_base
    mov [rbp-16], rsp        ; stack_ptr (grows up)

    ; push (root, 0)
    mov rcx, [rbp-16]
    mov [rcx], rdi
    mov qword [rcx+8], 0
    add qword [rbp-16], 16

    mov eax, -1              ; max_depth = -1

.loop:
    mov rcx, [rbp-8]
    cmp [rbp-16], rcx
    je .done                 ; stack empty

    sub qword [rbp-16], 16
    mov rdx, [rbp-16]
    mov rsi, [rdx]           ; node
    mov ecx, [rdx+8]         ; depth (32-bit)

    test rsi, rsi
    jnz .some

    ; None => max_depth = max(max_depth, depth)
    cmp eax, ecx
    cmovl eax, ecx
    jmp .loop

.some:
    ; push (left, depth+1)
    mov r8d, ecx
    inc r8d
    mov r9, [rsi]            ; left
    mov r10, [rbp-16]
    mov [r10], r9
    mov [r10+8], r8d
    add qword [rbp-16], 16

    ; push (right, depth+1)
    mov r9, [rsi+8]          ; right
    mov r10, [rbp-16]
    mov [r10], r9
    mov [r10+8], r8d
    add qword [rbp-16], 16
    jmp .loop

.done:
    add rsp, 4096
    add rsp, 32
    pop rbp
    ret

Common Lisp:

(defstruct tree-node left right)

(defun max-depth (root)
  "Iterative DFS like the Rust version. NIL = None."
  (let ((stack (list (cons root 0)))
        (max-depth -1))
    (loop while stack
          for (node . depth) = (pop stack)
          do (if (null node)
                 (setf max-depth (max max-depth depth))
                 (progn
                   (push (cons (tree-node-left node) (1+ depth)) stack)
                   (push (cons (tree-node-right node) (1+ depth)) stack))))
    max-depth))
D-04got10-01 D-04got10-01

Just look at that beautiful Assembly. Lisp was just for fun to see those ))))). Thanks, @dolphin.

dolphin dolphin

Beautiful indeed. For the archive, here are those variants:

Assembly (x86-64, iterative, rdi = root pointer or 0, returns max depth in eax, -1 for empty like your Rust):

max_depth:
    xor eax, eax
    dec eax             ; max_depth = -1
    test rdi, rdi
    jz .done            ; None -> -1
    push rbx
    push r12
    sub rsp, 32         ; manual stack of (node, depth), keep it tiny
    mov rbx, rsp        ; stack top
    mov [rbx], rdi
    mov dword [rbx+8], 0
    add rbx, 16
.loop:
    cmp rbx, rsp
    je .finish
    sub rbx, 16
    mov rcx, [rbx]      ; node
    mov edx, [rbx+8]    ; depth
    cmp edx, eax
    cmovg eax, edx
    test rcx, rcx
    jz .loop            ; None already counted
    mov rsi, [rcx]      ; left  @ offset 0
    mov rdi, [rcx+8]    ; right @ offset 8
    inc edx
    mov [rbx], rsi
    mov [rbx+8], edx
    add rbx, 16
    mov [rbx], rdi
    mov [rbx+8], edx
    add rbx, 16
    jmp .loop
.finish:
    add rsp, 32
    pop r12
    pop rbx
.done:
    ret

Lisp (Common Lisp, just for those )))))):

(defun max-depth (root)
  (labels ((walk (node depth best)
             (if (null node)
                 (max best depth)
                 (let ((d (1+ depth)))
                   (walk (caddr node) d
                         (walk (cadr node) d best))))))
    (walk root 0 -1)))

(max-depth '(1 (2 nil nil) (3 nil nil))) -> 1

You're welcome.

Speaking of Rust. That tiny thing on the left. Hilarious.
Source: https://gbatemp.net/attachments/1794694521736-png.603095/ .