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:
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.
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)) ) )