When I interviewed at Microsoft in Seattle for an SDE Internship, I was stuck on the last interview question. After taking CMPUT 325 (Functional Programming) at the University of Alberta, I realized that I could solve the problem with only a few lines of Common Lisp.

Given a tree, like the one on the right, find your Nth neighbour to the right. For example, if you want to find the 2nd neighbour to the right of -4, you'll get the 21 node.

There are some subtleties to the problem:

- The tree does not have to be full
- Your neighbour does not have to share the same parent

Here's the solution that I gave in the interview:

Assume that each node only has two children. Assign the "left path" (aka, the pointer to the left child) a "code" of zero. Assign the "right path" a code of one. Notice that any node n-levels deep in the tree can be accessed by an n-"bit" code.

This n-bit code can be given as a bitfield to a recursive function which follows the pointers down the the desired level.

- In the case that the tree is full, to find the nth right neighbour, one does a search through the tree, keeping track of the pointers followed, to find your starting node. Next, take that node and add (n)base-2 to it to arrive at an "instruction" that will guide you into the desired node.
- If the tree is not full, then there's an interesting issue. Adding (n)base-2 will work still, but the pointer-follower function will need to take in mind the following scenario:
- If the proposed pointer-follow is invalid, add 1 to the given bitfield and try again.

Magic things with BFS, and putzing with the queue.

Description to follow

` ````
;;
;; Stefan Martynkiw
;; March 22, 2015
;; The following code is under the Apache2 License
;;
; Find n-th neighbour to right in list
;Tree with duplicates
"
/-- 4----\
3 2
/ \ / \
1 5 3 8
| / \ | \ / \
6 7 3 0 1 10 11
"
;Our test tree is drawn above, represented below
(setq tree '( ( ( (nil 6 nil ) 1 nil ) 3 ( (nil 7 nil ) 5 (nil 3 nil) ) )
4
( ((nil 0 nil) 3 (nil 1 nil) ) 2 ((nil 10 nil) 8 (nil 11 nil) ) )
)
)
;Test Tree without duplicates
"
/-- 1----\
2 3
/ \ / \
4 5 6 ----- 7
| / \ | ----\ / \
8 9 10 11 12 13 14
"
;Our test tree is drawn above, represented below
(setq tree2 '( ( ( (nil 8 nil ) 4 nil ) 2 ( (nil 9 nil ) 5 (nil 10 nil) ) )
1
( ((nil 11 nil) 6 (nil 12 nil) ) 3 ((nil 13 nil) 7 (nil 14 nil) ) )
)
)
(defun solve-problem (G N J)
;Given Tree G, Node N, find the Jth neighbour to the right
(get-Jth-neighbour-to-N
(get-all-neighbours G (find-node G N 0) 0) ; Get's list of all things at N's level
N
J
)
)
;G is the given Tree
;R is the number of levels deep in recursion we need to be at (find it with find-node)
;F is the levels deep we're currently at
; Keep around as a variable the base tree so that when we're done recursing, that's all.
(defun get-all-neighbours (G R F)
;
; At each level, look at R, if R < F, recurse down,
; If R = F then return (append (each_node_at_this_level) )
(let ( (left-subtree (car G))
(right-subtree (caddr G))
(nodeval (cadr G))
(nextF (+ F 1))
)
(cond
( (eq R F)
(cond
((null nodeval) nil) ;Prune NILs from output list
(T
(append (list nodeval))
)
)
)
( (> F R)
;If we've recursed farther than we need to, then we're done
nil
)
(T
(append
(get-all-neighbours left-subtree R nextF)
(get-all-neighbours right-subtree R nextF)
)
)
)
)
)
;If you want K to be zero-indexed, call this function with accum=0
;If you want K to be 1-indexed, call this function with accum=1
(defun get-kth-item-from-list (L K accum)
(cond
((eq accum K) (car L))
(T
(get-kth-item-from-list (cdr L) K (+ 1 accum))
)
)
)
;Given a tree G, find node N, and return levels deep in variable R
;Pretty much DFS.
;Kinda buggy.
;If there are duplicate nodes, the strange behavior happens.
;The -1 trick is really gross. The recursive call used to evaluate to nil if there wasn't a match.
;However, there were bugs with that value propigating up depending on which half of the tree
;the actual value was found. Where the (max) call is, I thought about using a let and a cond to always
;just return a non-nil value, but because of the (+ 1 R) trick, the value of R would be unexpectedly
;incremented while evaluating the (cond).
;
;This solution is acceptible providing that there are no duplicate elements in the tree.
(defun find-node (G N R)
(cond
((null G) -1)
((atom G) -1)
(T
(let ( (left-subtree (car G))
(right-subtree (caddr G))
(nodeval (cadr G))
)
(cond
((eq nodeval N) R) ;We've found our desired node. Return R.
(T
;If we're here, our current level didn't contain the desired node.
;As the function was written, it returned nil if the subtree search failed. It returns an
;appropriate R if the search was successful. The (max) below causes find-node
;to return an appropriate value
(max
(find-node left-subtree N (+ 1 R) )
(find-node right-subtree N (+ 1 R) )
)
)
)
)
)
)
)
(defun get-Jth-neighbour-to-N (L N J)
;List L, desired node N, J is zero-indexed index-N++ ,I is accumulator storing item
(cond
((eq (car L) N)
;We're at the desired start-point
(cond
((> J 0)
;Keep going
(get-Jth-neighbour-to-N (cdr L) (cadr L) (- J 1) )
)
(T
;Return where the item where we're at
(car L)
)
)
)
(T
(get-Jth-neighbour-to-N (cdr L) N J )
)
)
)
;Does list L contain Item I?
(defun contains (L I)
(cond
((null L) nil)
((eq I (car L)) T)
(T (contains (cdr L) I))
)
)
```

#### Lisp File

Download the above LISP source code..

Contents (c) Copyright Stefan Martynkiw 2005-2011

Hosted on University of Alberta Webspace

Hosted on University of Alberta Webspace