find_prev_tree_node.rb

class Node
  attr_accessor :parent, :left, :right, :value

  def is_leaf?
    left.nil? && right.nil?
  end

  def has_left_child?
    !left.nil?
  end

  def find_prev
    if has_left_child?
      # no point in going right as it only increments
      # we have a left child...
      # everything in that branch should be less. lets explore that way
      next_child_node(left)
    else
      # no where to go but up
      next_parent_node(parent)
    end
  end

  def next_parent_node(node)
    if node.value > value
      # we are a left child. the previous is further up the tree
      next_node(node.parent)
    else
      # we are a right child. nodes only get less from here so we stop.
      node
    end
  end

  def next_child_node(node)
    if node.right
      # the right node is still less than starting node but greater than current child.
      # Go that way...
      next_child_node(node.right)
      # and keep going right until no more rights
      # everything right from here on is less than the starting node...
      # while its still incrementing and getting closer to starting node
    else
      # if there is no right child, we have reach our destination...
      # they only get smaller from here if we went left
      node
    end
  end

end

tree examples.txt

https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/pix/insertEx.bmp
http://1.bp.blogspot.com/-Yey30umBqHo/VpGKByQSLmI/AAAAAAAAIDo/SOzA15q-uqA/s1600/binary%2Btree.png
http://www.includehelp.com/data-structure-tutorial/images/binary-tree.jpg