1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Normally a tree has a single node at the top and many leaf nodes at the bottom. However, your tree appears to be "upside-down" where the top level has many nodes and as you traverse the tree you arrive at one (or more) common roots. (Each node only has child nodes but you talk about finding it's ancestor, which typically is a parent). Is this what you intend? \$\endgroup\$ – Zack Apr 14 '16 at 18:29
  • \$\begingroup\$ Which part of the code makes you think that? Each node has a value, a left branch, and a right branch, so it wouldn't be possible to traverse the tree upside down with this code. \$\endgroup\$ – JonathanR Apr 14 '16 at 21:08
  • \$\begingroup\$ Ancestor usually implies parent, but your nodes only reference children (left and right). Assume I have a simple tree where A->AA, BB; AA->AAA, BBB; BB->CCC, DDD. A is the common ancestor of all nodes. If I want to store a reference to the tree, I only need to pass A around. If I start at AAA, I cannot backtrack to A because AAA has no parent/ancestor reference. Yet your code is looking for an ancestor. If I "flip it upside-down" [AAA, BBB, CCC, DDD] become the "root" nodes (which conflicts with the standard definition of a tree). I can now find an ancestor, assuming these nodes fan in. \$\endgroup\$ – Zack Apr 14 '16 at 21:20
  • \$\begingroup\$ I think its your terminology that is throwing me off. After staring for a bit, if looks like you are just looking for a node with given left and right values, is that correct? \$\endgroup\$ – Zack Apr 14 '16 at 21:24
  • \$\begingroup\$ You can still find whether node A is node B's parent by starting from node A and seeing if you can find node B somewhere in its children. If starting at node A I can find both node B and node C, then node A is a common ancestor of B and C. The problem is to find their "first" common ancestor (the one lowest in the tree). \$\endgroup\$ – JonathanR Apr 14 '16 at 21:26
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ thanks but not using a parent node is part of the exercise. \$\endgroup\$ – JonathanR Apr 18 '16 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.