Binary Tree Ancestor

binaryTree

class Node
  constructor: (val) ->
    @val = val
    @left = null
    @right = null

findAncestors = (node, val, arr) ->
  return false if node == null
  if node.val == val
    return arr.push(val)
  left = findAncestors(node.left, val, arr)
  if left
    arr.push(node.val)
  right = findAncestors(node.right, val, arr)
  if right
    arr.push(node.val)
  return arr if left || right
  false

commonAncestor = (tree, val1, val2) ->
  ancestors1 = findAncestors(tree, val1, [])
  ancestors2 = findAncestors(tree, val2, [])
  node1 = ancestors1.pop()
  node2 = ancestors2.pop()
  parent = null

  while(node1 != val1 && node2 != val2)
    if node1 == node2
      parent = node1
    if ancestors1.length > ancestors2.length
      node1 = ancestors1.pop()
    else if ancestors1.length < ancestors2.length
      node2 = ancestors2.pop()
    else
      node1 = ancestors1.pop()
      node2 = ancestors2.pop()

  parent

# create a binary tree from a specific graph

binTree = new Node(7)
binTree.left = new Node(9)
binTree.left.left = new Node(2)
binTree.left.right = new Node(1)
binTree.right = new Node(4)
binTree.right.left = new Node(8)
binTree.right.left.left = new Node(6)
binTree.right.right = new Node(3)
binTree.right.right.right = new Node(5)

# test for ancestors

ancestors = findAncestors(binTree,6, [])
console.log ancestors # [6, 8, 4, 7]

# test for common ancestors
parent = commonAncestor(binTree, 1, 2)
console.log parent # 9

parent = commonAncestor(binTree, 1, 5)
console.log parent # 7

parent = commonAncestor(binTree, 5, 6)
console.log parent # 4