0

I believe my code works in one scenario and breaks in another for the Leetcode problem #501 due to gaps in my understanding of recursion and pass-by-reference concepts in Ruby.

Using instance variables, the following code works:

def find_mode(root)
  return [] if root.nil?
  @modes = []
  @counter = 1
  @max = 0
  @prev = nil
  inorder(root)
  @modes
end

def inorder(node)
  return if node.nil?

  inorder(node.left)

  if !@prev.nil?
    if @prev.val == node.val
      @counter += 1
    else
      @counter = 1
    end
  end

  if @counter > @max
    @max = @counter
    @modes = [node.val]
  elsif @counter == @max
    @modes << node.val
  end

  @prev = node

  inorder(node.right)
end

However, the following alternate version does not work. Instead it times out.

def find_mode(root)
  return [] if root.nil?
  modes = []
  counter = 1
  max = 0
  prev = nil

  inorder(root, modes, prev, counter, max)
  modes
end

def inorder(node, modes, prev, counter, max)
  return if node.nil?
  inorder(node.left, modes, node, counter, max)

  if !prev.nil?
    if prev.val == node.val
      counter += 1
    else
      counter = 1
    end
  end

  if counter > max
    max = counter
    modes = [node.val]
  elsif counter == max
    modes << node.val
  end
  prev = node

  inorder(node.right, modes, node, counter, max)
end

What am I failing to understand in the second approach?

lctofaang
  • 1
  • 1
    What is leetcode problem 501? Please post a complete question statement. – Pascal Mar 08 '20 at 19:25
  • Can you give us an example dataset and what the recursive function sets out to do? – Rystraum Mar 08 '20 at 20:10
  • In any case, you can check this https://stackoverflow.com/a/23421320/365218 – Rystraum Mar 08 '20 at 20:15
  • The problem and the dataset can be found here: https://leetcode.com/problems/find-mode-in-binary-search-tree/ . Most likely, it is easiest to interact with their editor, instead of setting up the environment yourself. The classes used are also on that page. – lctofaang Mar 08 '20 at 21:21
  • lctofaang, when asked for clarification (e.g., what is Leetcode 501?), please respond by editing your question rather than answer in comments. Questions should be self-contained and not all readers read all comments. – Cary Swoveland Mar 08 '20 at 21:37

0 Answers0