Twitter Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
If you want just one query, just use a breadth first search from the first node until the second node is found.
binary tree by default is a directed acyclic graph with a distinguished node (root) that has 0 in-degree
so how do you do BFS from a non-root node to another non-root node?
yes it is, but the nodes usually have a pointer to its parent. you can use that.
this pointer is used for situations like deleting elements of the tree and is also useful here
First find the path (starting from root) for the first node , then the same for the second node. Then find the lowest common ancestor and the number of nodes in the requested path.
ArrayList<Node> find_path(Node current , Node n, ArrayList<Node> path){
path.add(current);
if (current == n)
return path;
if (current.left != null){
ArrayList<Node> p1 = find_path(current.left , n , path);
if (p1 != null)
return p1;
}
if (current.right != null){
ArrayList<Node> p2 = find_path(current.right , n , path);
if (p2 != null)
return p2;
}
path.remove(path.remove(path.size() - 1));
return path;
}
int find_path_nodes(Node root , Node n1 , Node n2){
ArrayList<Node> p1 = find_path(root , n1 , new ArrayList<Node>());
ArrayList<Node> p2 = find_path(root , n2 , new ArrayList<Node>());
int i = 0;
for (; i < Math.min(p1.size() , p2.size()) ; i++){
if (p1.get(i) != p2.get(i))
break;
}
return p1.size() + p2.size() - 2 * i + 1;
}
struct tree_t {
tree_t *left, *right;
int val;
};
tree_t *get_anchor(tree_t *root, int x, int y) {
if (root->val >= x && root->val <= y)
return root;
else if (root->val < x)
return get_anchor(root->right, x, y);
else
return get_anchor(root->left, x, y);
}
int get_len_one(tree_t *root, int x, int len) {
if (root->val == x)
return len;
else if (root->val < x)
return get_len_one(root->right, x, len+1);
else
return get_len_one(root->left, x, len+1);
}
int get_len(tree_t *root, int x, int y) {
tree_t *anchor = get_anchor(root, std::min(x,y), std::max(x,y));
return get_len_one(anchor, x, 0) + get_len_one(anchor, y, 0);
}
Here's an algorithm that combine LCD with distance between two nodes.
public static Integer nodeDistance(Node root, int targetA, int targetB, int distance) {
if (root == null)
return null;
if (root.data == targetA || root.data == targetB)
return distance;
Integer leftCount = nodeDistance(root.left, targetA, targetB, distance + 1);
Integer rightCount = nodeDistance(root.right, targetA, targetB, distance + 1);
if (leftCount != null && rightCount != null)
return leftCount + rightCount - (2 * distance);
return leftCount == null ? rightCount : leftCount;
}
Here is a Scala example, including Tree implementation. I thought of a way to optimize (will update later), feedback welcome:
import scala.annotation.tailrec
object questions extends App {
sealed trait Tree[+T] {
//find the distance from this node to the given descendant. zero if nodes are equal.
def depthTo[T](dest: T, counter: Int = 0): Option[Int] = this match {
case End => None
case Node(v, left, right) =>
if(v == dest)
Some(counter)
else
left.depthTo(dest, counter + 1) orElse { right.depthTo(dest, counter + 1) }
}
}
case class Node[+T](value: T, left: Tree[T], right: Tree[T]) extends Tree[T]
case object End extends Tree[Nothing]
object Node {
def apply[T](value: T): Node[T] = Node(value, End, End)
}
def distance(root: Node[Int], n1: Int, n2: Int): Int = {
//generate a path (i.e. list of nodes) from the start to the destination. O(n)
def findPath[T](curr: Tree[T], path: List[Node[T]] = List()): List[Node[T]] = curr match {
case End => path
case nn @ Node(v, left, right) =>
if(v == n1) nn :: Nil
else {
val p = nn :: findPath(left, path)
if(p.isEmpty)
nn :: findPath(right, path)
else
p
}
}
//find shortest path from a list of nodes to a given destination node.
@tailrec
def findDist[T](path: List[Node[T]], counter: Int = 1): Int = path match {
case Nil => throw new Exception("invalid binary tree: no path between nodes")
case hd :: tl =>
hd.depthTo(n2) match {
case None => findDist(tl, counter + 1)
case Some(i) => i + counter
}
}
findDist(findPath(root).reverse)
}
val ex1 = Node(1, Node(2, Node(4), Node(5)), Node(3))
println(distance(ex1, 2, 4))
}
int findbnodes(TNode* node, int k1, int k2)
{
int minv = -1;
findbnodes(node, k1, k2, 1, minv);
return minv;
}
int findbnodes(TNode* node, int k1, int k2, int cdepth, int &minv)
{
if (node == NULL)
{
return -1;
}
int ldepth = findbnodes(node->left, k1, k2, cdepth + 1, minv);
int rdepth = findbnodes(node->right, k1, k2, cdepth + 1, minv);
if (node->val == k1 || node->val == k2)
{
if (ldepth > 0)
{
minv = ldepth - cdepth + 1;
}
else if (rdepth > 0)
{
minv = rdepth - cdepth + 1;
}
return cdepth;
}
else if (ldepth >0 && rdepth > 0)
{
minv = ldepth - cdepth + rdepth - cdepth + 1;
return ldepth;
}
else if (ldepth >0)
{
return ldepth;
}
else if (rdepth >0)
{
return rdepth;
}
return -1;
}
traverse the tree to find the two nodes and search for int *A, int *B:
if node == *A (or *B )and the other pointer is 0, return 1
else if node == *A (or *B )and the other pointer is NOT 0, return (recurse with A = 0)
else if one of A / B is zero, return (recurse + 1)
else if both are none zero return the sum of recurse_left, recurse_right
recursion decision based on value of *A, *B and current node, basically a binary search tree type situation
public int findPathLength(Node left, Node right) {
If ( left == null || right == null)
throw new IllegalArgumentException();
if ( left == right )
return 0;
Node leftParent = left.getParent();
Node rightParent = right.GetParent();
if ( leftParent == rightParent )
return 1;
return 2+ findPathLength(leftParent, rightParent);
}
class NodeLength{
public:
int result = -1;
int findNode(TreeNode* root, TreeNode* nd1, TreeNode* nd2, int len){
if(root == NULL) return 0;
int plen1 = findNode(root->left, nd1, nd2, len+1);
int plen2 = findNode(root->right, nd1, nd2, len+1);
if(result == -1){
if(plen1 != 0 && plen2 != 0){
result = plen1 + plen2;
return result;
}
if(root == nd1){
if(plen2 != 0){
result = plen2 - len;
return result;
}else
return len;
}
if(root == nd2){
if(plen1 != 0){
result = plen1 - len;
return result;
}
return len;
}
if(plen1 != 0) return plen1;
if(plen2 != 0) return plen2;
return 0;
}
return 0;
}
int driver(TreeNode* root, TreeNode* nd1, TreeNode* nd2){
findNode(root, nd1, nd2, 0);
return result;
}
};
public class TreeDistance {
class Node {
int v;
Node left, right;
public Node(int v){
this.v = v;
left = right = null;
}
}
public TreeDistance() {
}
static List<Node> pathToNode(Node root, Node n){
if(root == null || n == null){
return null;
}
List<Node> result = new LinkedList<Node>();
if(root == n){
result.add(n);
} else {
List<Node> subRes = null;
if(root.left != null){
subRes = pathToNode(root.left, n);
if(subRes != null){
result.add(root);
result.addAll(subRes);
}
}
if(subRes == null && root.right != null){
subRes = pathToNode(root.right, n);
if(subRes != null){
result.add(root);
result.addAll(subRes);
}
}
if(subRes == null){
result = null;
}
}
return result;
}
static int computeTreeDistance(Node root, Node n1, Node n2) throws Exception{
if(root == null || n1 == null || n2 == null){
throw new IllegalArgumentException();
}
List<Node> pathToN1, pathToN2;
pathToN1 = pathToNode(root, n1);
pathToN2 = pathToNode(root, n2);
// one of nodes not present
if(pathToN1 == null || pathToN2 == null){
throw new Exception("One of the nodes not in the tree");
}
int d1 = pathToN1.size(), d2 = pathToN2.size();
int res = d1 + d2;
boolean done = (d1==0 || d2==0) || (pathToN1.get(0) != pathToN2.get(0));
while(!done){
res = res-2;
pathToN1.remove(0);
pathToN2.remove(0);
}
return res;
}
}
1. find the lowest common denominator between these two nodes.
- moiskim September 19, 20132. find the distance between LCD to the first node,
3, find the distnace between LCD to the second node.
4. Add these two distances.