# Common ancestor in a binary tree

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

• 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?
– Zack
Apr 14, 2016 at 18:29
• 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. Apr 14, 2016 at 21:08
• 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.
– Zack
Apr 14, 2016 at 21:20
• 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?
– Zack
Apr 14, 2016 at 21:24
• 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). Apr 14, 2016 at 21:26

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

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

• thanks but not using a parent node is part of the exercise. Apr 18, 2016 at 18:51