next_right_ptr.rb

class Node
  attr_accessor :next, :left_child, :right_child
end

def add_next_right_ptrs(node, right_sib)
  node.next = right_sib || nil
  if node.left_child
    add_next_right_ptrs(node.left_child, right_sib=node.right_child)
  end
  if node.right_child
    if right_sib
      add_next_right_ptrs(node.right_child, right_sib=right_sib.left_child)
    else
      add_next_right_ptrs(node.right_child, nil)
    end
  end
end

def build_tree num_levels
  root = Node.new
  if num_levels > 1
    root.left_child = build_tree num_levels - 1
    root.right_child = build_tree num_levels - 1
  end
  root
end