Mathematical thinking and how to solve "lowest common ancestor"

It is quite possible on your interview to have questions related to (binary) trees. Here is one that I have on mine a year ago.

Given values of two nodes in a Binary Tree, write a c program to find the Lowest Common Ancestor (LCA).

The solution that I will present is not optimal, but did the job. Most interesting is how I found the solution using technique described in the book
Thinking Mathematically
On interview I implement it in Python but here I will use Common Lisp. Let's start time is up. Here is the scheme from the book that I follow:

ENTER

It is strange that representation is not given so the first question is: How to represent a tree in Common Lisp?

The easiest way is as nested list. For example:

(1 (2 (6 7)) (3) (4 (9 (12))) (5 (10 11)))

The first element of a list is the root of that tree (or a node) and the rest of the elements are the subtrees (every new open parenthesis is a next level of the tree). For example, the subtree (6 7) is a tree with 2 at its root and the elements 6 7 as its children. So I start digging on this.
Another representation that I found is to use Paul Graham "ANSI Common Lisp" representation:

(defstruct node
  elt (l nil) (r nil))

I usually create a lisp file and start codding, trying and testing. Sometime I receive strange errors.
As you know defstruct in Lisp also defines predicates e.g. node-p. It is possible to clash names easily. Word node is quite used when we talk for trees.
Doing this SBCL returns bizarre message:

caught WARNING:
  Derived type of TREE is
    (VALUES NODE &OPTIONAL),
  conflicting with its asserted type
    LIST.
  See also:
    The SBCL Manual, Node "Handling of Types"

REMEMBER

DO NOT forget to comment unused code!

Because I have binary tree may be a better way to represent it with nested lists is to use 'a-list' (more readable). For example:

(1 (2 (6 . 7)) (3) (4 (9 (12))) (5 (10 . 11))).

Even better - display empty:

(0 (1 (2 . 3) NIL) (4 (5 (6) NIL) NIL))

What is a node? (elm (left right))

This is not consistent - (left right) could not be treated as 'elm'. Let's fix it:

(0 (1 (2) (3)) (4 (5 (6))))

Great now I have the tree!

;; Format is ugly but more like a tree
(defparameter *bin-tree* '(0
                           (1
                            (2) (3))
                           (4
                            (5
                             (6)))))

GENERALIZE

(defun make-bin-leaf (elm)
  "Create a leaf."
  (list elm))

(defun make-bin-node (parent elm1 &optional elm2)
  (list parent elm1 elm2))

;; simple creation test
(deftest test-make-bin-tree ()
  (check
    (equal (make-bin-node 0 (make-bin-node 1 (make-bin-leaf 2)
                                           (make-bin-leaf 3))
                          (make-bin-node 4 (make-bin-node 5 (make-bin-leaf 6))))
           '(0 (1 (2) (3)) (4 (5 (6) NIL) NIL)) )))

INTRODUCE

Define what is node and leafs (not during the interview time is up)

(defun node-elm (node)
  (first node))

(defun node-left (node)
  (first (second node)))

(defun node-right (node)
  (first (third node)))

(deftest test-nodes ()
  (check
    (eq (node-left '(1 (2) (3))) 2)
    (eq (node-right '(1 (2) (3 (4) (5)))) 3)
    (eq (node-right 1) nil)
    (eq (node-elm '(1)) 1)
    (eq (node-elm nil) nil)))

;;; Predicates

(defun leaf-p (node)
  "Test if binary tree NODE is a leaf."
  (and (listp node)
       (= (list-length node) 1)))

(defun node-p (node)
  "Test if binary tree node is a node with children"
  (not (leaf-p node)))

;; wishful thinking ;) 
(defun member-p (elm tree)
  (eq (find-anywhere elm tree) elm))

AHA!

I discover that it very easy to write 'find-anywhere' when we present trees as nested lists this: (0 (1) (2)) 'car' is the current 'cdr's
are the successors and we stop when 'car' is an atom. There is no need to remember DFS.

(defun find-anywhere (item tree)
  "Does ITEM occur anywhere in TREE?
Returns searched element if found else nil."
  (if (atom tree)
      (if (eql item tree) tree)
      (or (find-anywhere item (first tree))
          (find-anywhere item (rest tree)))))

(deftest test-member-p ()
  (check
    (eq (member-p 6 *bin-tree*) t)))

Good job! (Cheer up yourself)

REMEMBER

Do not make big steps test carefully everything!

ATTACK

Now I have a tree and I can concentrate on solving the problem.

SIMPLIFY

From where to start? As a rule I start from easiest case - one root and two leafs. In this case task is easy. If (root (p) (q)) then 'root' is the parent.

INTRODUCE

1. Names for the searched leafs: 'p' and 'q'
2. Method signature: (defun lca (root p q) ...)

Concentrate on (elm (left) (right)) and because this is the simplest case apply rule for the rest. From my previous experience I know that binary
trees are recursive structure so recursion will pass perfectly. Of course be careful how to terminate.

Algorithm could be:
- find first in a left sub-tree
- find second in a right sub-tree
- compare to the searched 'p' and 'q'

STUCK

How to track context? I could find easily element but I have to know its parent. Some how context should be created.

Is it possible to use recursion to create context?
A tree is a collection of smaller trees up to a simple node. In the same way that a list is a collection of smaller list.
We reduce 'elm'(it is tricky to choose proper name could be e.g. 'tree-branch-node-leaf-nil') so it is possible to be node, leaf or null. Wait a minute...

AHA! I could build the recursive algorithm using possible 'elm' values:

(lca-rec nil 1 2)
                         (lca-rec '(1) 1 2)
                         (lca-rec '(0 (1) (2)) 1 2)

And I can even use them also for tests.

Concentrate on the small picture - only one node.

;; if elm is null or leaf
(defun lca-rec (elm p q)
  (cond ((null elm) nil)
        ((or (eq (car elm) p)
             (eq (car elm) q)) elm)
        ;...
        ))

More difficult part - if it is a node (elm (p) (q))

(defun lca-rec (elm p q)
  (cond ((null elm) nil)
        ((or (eq (car elm) p)
             (eq (car elm) q)) elm)
        (t (let ((left (cadr elm))      ; ***
                 (right (caddr elm)))   ; ***
             (when (and left right)     ; ***
                 (car elm))))))         ; ***

Now I have a tree - the same solution recursively and reduce 'elm'

(defun lca-rec (elm p q)
  (cond ((null elm) nil)
        ((or (eq (car elm) p)
             (eq (car elm) q)) elm)
        (t (let ((left (lca-rec (cadr elm) p q))     ; ***
                 (right (lca-rec (caddr elm) p q)))  ; ***
             (when (and left right)
               (car elm))))))

What we have after recursion?
After recursion we are finished with current 'segment' from the big picture.

Is it possible to discover nothing?
YES! Because with recursion we do not traverse the whole tree.

But elements could be on different levels so I somehow to pass trough recursive calls what is found. That is OK, what I return from recursion is passed to the next recursive step.

AHA!

Now the better question is when it fails? Only when one or none elements are found.
Should I return if only one element is found? YES!

REMEMBER. Look at the recursive procedure as simplest part of something big. Recursive call is the glue to the big picture.

In our case:

.. ((left (lca-rec (cadr elm) p q))
    (right (lca-rec (caddr elm) p q))) ...

finds only 'left' or 'right' of the current node it doesn't search the whole tree. It seems like - but it is not true. That's why I have to return what is fond in current 'node' and the recursion will pass it to the next level until
both are found or not. Finally we have:

(defun lca-rec (elm p q)
  (cond ((null elm) nil)
        ((or (eq (car elm) p)
             (eq (car elm) q)) elm)
        (t (let ((left (lca-rec (cadr elm) p q))
                 (right (lca-rec (caddr elm) p q)))
             (if (and left right) (car elm)
                 ;; return what is found until now and hope other will be found on next iteration
                 (or left right))))))        ;; ***

Done. It seems difficult at first but when practice a while solving such problems are fun.

Python Functional Programming

Lecture 1
Lecture 2

# Do you remember this code from previous lecture (lecture 2)
def make_adder(n=1):
    return lambda x: x + n

one_adder = make_adder() # actually creates: one_adder = lambda x: x + 1
one_adder(1)

"""
1. List/Dict comprehension

"""

# [{do job using 'for' variable} {'for' cycle} {filter predicate (optional)}]

# for lists
i_all = [i for i in range(0, 10)]
i_all_even = [i for i in range(0, 10) if i % 2 == 0]

# for dict
x_squared_dict = {item: item * item for item in range(0, 4)}

"""
2. Map (aka transform) function

map: this function takes a unary function and some list/iterable
of values and produces a list/iterable of mapped/transformed values based on
substituting each value with the result of calling the parameter function
on that value.

map({function}, {iterable+}) returns transformed sequence
"""

map(lambda x : x**2, range(1, 5))
map(lambda x,y: x*y, range(1, 5), range(1, 5))

"""
3. Filter (aka accumulate)

filter: this function takes a predicate (a unary function returning a bool)
and some list/iterable of values and produces a list/iterable with only
those values for which the predicate returns True.

filter({predicate function}, {iterable})
"""

# filter({predicate for even}, [i for i in range(2,50)])

def is_even(x):
    return x % 2 == 0

# Remember how function is passed
filter(is_even, [i for i in range(2,50)])

# Using lambda. Do not forget () around!
filter((lambda x: x % 2 == 0), [i for i in range(2,50)])

"""
4. Reduce

reduce: this function is different than the previous two: it
takes a binary function and some list/iterable of values and typically produces
a single value: it reduces or accumulates its arguments into a single value.

By default, the first item in the sequence initialized the starting value.
"""

# function with two parameters is a binary function
reduce((lambda x, y: x * y), range(1, 5))
# (((1 * 2) * 3) * 4)

# Here is the 'for' loop version
L = range(1, 5)
result = L[0]
for x in L[1:]:
    result = result * x
    print result

reduce(lambda x,y : x - y, [1, 2, 3])
# ((1 - 2) - 3)

# NOTE: Technically, this is called LEFT reduction/accumulation because the operators are
# applied left to right.

def max(x, y):
    return x if x > y else y

# Then, calling

reduce(max, [4, 2, -3, 8, 6])

# is equivalent to max(max(max(max(4,2),-3),8),6) which evaluates (left to right)
# as follows, to compute the maximum of the entire list of values.
#
# max(max(max(max(4,2),-3),8),6) -> max(max(max(4,-3),8),6) ->
# max(max(4,8),6) -> max(8,6) -> 8

# Here is a concrete example of a function style of programming, using map,
# filter, and reduce.

# This expression computes the length of the longest line in
# a file.
reduce(max, map(lambda l: len(l.strip()), open('recursion.txt')))

# To return the longest line, not the length of the longest line, we could alter
# the computation slightly, as follows.
reduce(lambda x,y: x if len(x) >= len(y) else y,
       map(lambda l: l.strip(), open('recursion.txt')))

# Collect all files that contains a word
filter(lambda x: 'Problems:' in x,                      # **fixed**
       map(lambda l: l.strip(), open('recursion.txt'))) # **fixed**

# REMEMBER: Your functions should be as general as possible!

def search_in(file_name):
    return filter(lambda x: 'Problems:' in x ,
              map(lambda l: l.strip(), open(file_name)))

# not so bad - you can pass any file
search_for_prblems = search_in('recursion.txt')
search_for_prblems

# even better search for a different text
def search_in(file_name, text):
    return filter(lambda x: text in x ,
              map(lambda l: l.strip(), open(file_name)))

search_for = search_in('recursion.txt', 'Define')
search_for

# Could we divide file from text?

# In fist phase we set file_name in second text => closures baby!

# Returns a function(closure with file_name fixed) with one parameter
def search_in(file_name):
    return lambda text: filter(lambda x: text in x ,
                           map(lambda l: l.strip(), open(file_name)))

search_for = search_in('recursion.txt')
search_for('Define')

# Tip: Think of map as equivalent to one 'for' cycle

# I. Let's write 'combine_all' from previous lecture homework in Lisp way

# 1. map(map({func(x, y)}, ylist), xlist)

# 2. map(map((lambda x,y: [x, y]), ylist), xlist)

# 3. Use closure to pre-set x:
#    map((lambda x: map((lambda y: [x, y])), ylist)), xlist)

# 4. Check up to now
def combine_all(xlist, ylist):
    return map((lambda x:
            map((lambda y: [x, y]), ylist)),
           xlist)

combine_all(['a', 'b'], [1, 2])
# return two lists: [[['a', 1], ['a', 2]], [['b', 1], ['b', 2]]]

# 5. flatten one level -> [[1, 2], [3, 4]] to become [1, 2, 3, 4]
import operator
def combine_all(xlist, ylist):
    return reduce(operator.add, (map((lambda x:
                                  map((lambda y: [x, y]), ylist)),
                                 xlist)))

# II. Let's write 'combine_all' from previous lecture homework in Python way

# list comprehension could be multi-level
def combine_all(xlist, ylist):
    return [[x, y] for x in xlist for y in ylist]

# Tip: Always use list comprehension when want to return list

'''
1. Kinds of iteration:
- for, while (iterators, generators)
- map (high order functions)
- recursion - we strive to be tail recursion(later in this lecture)
'''

'''
2. What is recursion?

Recursion is a programming technique in which a call to a function results in
another call to that same function. Recursion means "defining something in terms of itself".

It is not only for functions - also for structures e.g. lists:

list = element | list
'''

# How can we present a list? list = element + rest of list
lst = [1, 2, 3]
lst2 = [lst[0]] + lst[1:]

# TIP: Remember that lst[0] returns element not list so we have to convert it to list!

# Do you remember that?
a = 'abc'
a[0]

# How about strings? It is a bit easy:
s = 'abc'
s2 = s[0] + s[1:]

'''
3. Lists and recursion

If you have list(string is also a list) data structure you can use recursion.
'''

# Here is how we structure recursive function:

# Phase One - stop condition
def reverse(s):
    if s == '':
        return ''
    else:
        # Recur to solve a smaller problem
        # Use the solution of the smaller problem to solve the original problem
        pass

# Phase Two - use rest of the list s[1:]
def reverse(s):
    if s == '':
        return ''
    else:
        # Use the solution of reverse(s[1:]) to solve the original problem
        pass

def reverse(s):
    if s == '':
        return ''
    else:
        return reverse(s[1:]) + s[0]

# Pythonic way using if

def reverse(s):
    return '' if s == '' else reverse(s[1:]) + s[0]

# Example
reverse('abcd')

'''
2. What is tail recursion and why it is better?

'''

# Which one is better - iteration or recursion?

def recsum(x):
    if x == 1:
        return x
    else:
        return x + recsum(x - 1)

# Evaluation description
#
# recsum(5)
# 5 + recsum(4)
# 5 + (4 + recsum(3))
# 5 + (4 + (3 + recsum(2)))
# 5 + (4 + (3 + (2 + recsum(1))))
# 5 + (4 + (3 + (2 + 1)))
# 15

# Not tail recursive either
def bad_factorial(n):
    if n == 0:
        return 1
    return n * bad_factorial(n - 1)


# Python limits the number of times any recursive function can call itself.

# Convert recursion to tail recursion introducing accumulator (aka pumping)

def factorial(n, accum=1):
    if n == 0:
        return accum
    else:
        return factorial(n - 1, n * accum)

# TCO (Tail Call Optimization) is the process by which a smart compiler can make a call to
# a function take no additional stack space.

# REMEMBER: Python do not do tail-call optimization!
# Read why: http://neopythonic.blogspot.pt/2009/04/tail-recursion-elimination.html