Common ancestor in a binary tree

Question

This method finds the common ancestor of two nodes in a binary tree.

Any style suggestions or ways to make it more idiomatic? Is the algorithm correct? Rubocop says the cyclomatic complexity is too high, how would you break this up?

class Node
  def initialize(value = nil, left = nil, right = nil)
    @value = value
    @left = left
    @right = right
  end
end

def common_ancestor(node, value1, value2)
  return node unless node
  return node if node.value == value1 || node.value == value2
  anc_left = common_ancestor(node.left, value1, value2)
  anc_right = common_ancestor(node.right, value1, value2)
  return node if anc_left && anc_right
  anc_left || anc_right
end

Answer 1

I think you can add functionality to Node to make the common ancestor search more ruby like. (I can add a search by value later, if you want.) I've added a parent member that is set automatically, and I've added each_parent and each_child_or_selfenumerators to enable easy traversal up or down the tree.

Note: Thinking about it, the search function needs a little more work in case node 2 is higher in the tree than node 1, but I am out of time right now. Let me know what you think. Testing indicates that this is not an issue.

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

    def initialize(value = nil, left = nil, right = nil)
        @parent = nil
        @value = value
        self.left = left
        self.right = right
    end

    def left=(node)
        unless node.nil?
            @left = node
            node.parent = self
        end
        @left
    end

    def right=(node)
        unless node.nil?
            @right = node
            node.parent = self
        end
        @right
    end

    def each_parent
        return enum_for(:each_parent) unless block_given?
        p = @parent
        while not p.nil?
            yield p
            p = p.parent
        end
    end

   def each_child_or_self
       return enum_for(:each_child_or_self) unless block_given?
       stack = [self]
       while not stack.empty?
           current = stack.pop
           stack.push current.left unless current.left.nil?
           stack.push current.right unless current.right.nil?
           yield current
       end
    end
end

The new search functions:

def common_ancestor(node1, node2)
    return nil if node1.nil? || node2.nil?
    return node1 if node1 == node2.parent
    return node2 if node2 == node1.parent
    node1_parents = node1.each_parent.to_a
    node2.each_parent { |p| return p if node1_parents.include? p }
    nil
end

def common_ancestor_by_value(root, value1, value2)
    return nil if root.nil?
    nodes = root
        .each_child_or_self
        .lazy
        .select { |n| n.value == value1 || n.value == value2 }
        .first(2)
    return nil unless nodes.length == 2
    common_ancestor(nodes.first, nodes.last)
end

And a test:

n41 = Node.new("DDD")
n42 = Node.new("EEE")
n43 = Node.new("FFF")
n44 = Node.new("GGG")
n21 = Node.new("BB", n41, n42)
n22 = Node.new("CC", n43, n44)
root = Node.new("A", n21, n22)

puts common_ancestor(n44, n21).value #common ancestor of 'GGG' and 'BB' is 'A'
puts common_ancestor(n21, n44).value #order doesn't matter
puts "---"
puts common_ancestor_by_value(root, "GGG", "BB").value #same applies when searching by value
puts common_ancestor_by_value(root, "BB", "GGG").value

Update 1: Added second enumerator and search function, fixed a bug

Update 2: Added lazy enumeration and profiled code against a tree with 10K nodes. Searching for nodes with values in the middle, the new lazy code runs about 2.5 times faster than the poster's original implementation. Also running rubocop, there are no Cyclomatic complexity warnings