Amazon Interview Question
SDE-2sCountry: India
public class BinTreeDistance {
private static class Node {
private int data;
Node left = null;
Node right = null;
public static class DataCount {
public int cnt = 0;
}
public Node (int level, DataCount dataCnt) {
if (level != 0) {
this.left = new Node(level - 1, dataCnt);
this.data = ++dataCnt.cnt;
this.right = new Node(level - 1, dataCnt);
}
else
this.data = ++dataCnt.cnt;
}
}
private Node tree = new Node(5, new Node.DataCount());
private int nodeDistance(Node root, int data) {
int x = -1;
if (root == null) {
return -1;
}
if (root.data == data || (x = nodeDistance(root.left, data)) > -1 || (x = nodeDistance(root.right, data)) > -1) {
return x + 1;
}
return -1;
}
private Node nodeLca(Node root, int left, int right) {
if (root == null) {
return null;
}
if (root.data == left || root.data == right)
return root;
Node lNode = nodeLca(root.left, left, right);
Node rNode = nodeLca(root.right, left, right);
if (lNode != null && rNode != null)
return root;
if (lNode != null)
return lNode;
if (rNode != null)
return rNode;
return null;
}
private int bstNodeDistance(Node root, int data) {
int x = -1;
if (root == null) {
return -1;
}
if (root.data == data)
return x +1;
if (root.data > data && (x = bstNodeDistance(root.left, data)) > -1){
return x + 1;
}
if (root.data < data && (x = bstNodeDistance(root.right, data)) > -1) {
return x + 1;
}
return -1;
}
private Node bstNodeLca(Node root, int left, int right) {
if (root == null) {
return null;
}
if (root.data > left && root.data > right)
return bstNodeLca(root.left, left, right);
if (root.data < left && root.data < right)
return bstNodeLca(root.right, left, right);
return root;
}
public static void main(String[] args) {
BinTreeDistance btd = new BinTreeDistance();
//btd.tree.printTree();
Node nLca = btd.bstNodeLca(btd.tree, 4, 45);
int ld = btd.bstNodeDistance(nLca, 4);
int rd = btd.bstNodeDistance(nLca, 45);
System.out.println();
System.out.println(ld + rd );
nLca = btd.nodeLca(btd.tree, 4, 45);
ld = btd.nodeDistance(nLca, 4);
rd = btd.nodeDistance(nLca, 45);
System.out.println(ld + rd );
}
}
An improved version of Kapil's answer. In their code, it is missed the case when n1 is subnode of n2
package com.careercup.ruslanbes.distance;
public class Main {
protected static int distance;
public static int distance(Node root, int n1, int n2) {
distance = 0;
if (n1 == n2) {
return 0;
}
findNodes(root, n1, n2);
return distance;
}
protected static int findNodes(Node root, int n1, int n2) {
if (root == null) {
return 0;
}
boolean isHere = root.data == n1 || root.data == n2;
int inLeft = findNodes(root.left, n1, n2);
int inRight = findNodes(root.right, n1, n2);
if (inLeft > 0 && inRight > 0) {
distance = inLeft + inRight;
return 0;
} else if (inLeft > 0) {
if (isHere) {
distance = inLeft;
return 0;
}
return inLeft+1;
} else if (inRight > 0) {
if (isHere) {
distance = inRight;
return 0;
}
return inRight+1;
} else if (isHere) {
return 1;
}
return 0;
}
}
Test Set:
package com.careercup.ruslanbes.distance;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;
class MainTest {
@Test
void distance1() {
Node root = new Node(0);
root.putLeft(101);
root.putRight(100);
assertEquals(2, Main.distance(root,100, 101));
assertEquals(2, Main.distance(root,101, 100));
assertEquals(1, Main.distance(root,0, 100));
assertEquals(1, Main.distance(root,0, 101));
}
@Test
void distance2() {
Node root = new Node(0);
Node left = root.putLeft(3);
left.putLeft(4)
.putLeft(100);
left.putRight(5);
root.putRight(6)
.putRight(101);
assertEquals(5, Main.distance(root,100, 101));
assertEquals(3, Main.distance(root,100, 5));
assertEquals(3, Main.distance(root,101, 3));
assertEquals(4, Main.distance(root,101, 4));
assertEquals(3, Main.distance(root,100, 0));
}
}
public class Distance
{
public int distance;
public bool xExists;
public bool yExists;
public Distance(int d, bool bx, bool by)
{
this.distance = d;
this.xExists = bx;
this.yExists = by;
}
}
public Distance FindRootDistance(TreeNode root, int x, int y)
{
if (root == null)
return new Distance(0, false, false);
if (x == y)
return new Distance(0, true, true);
Distance LeftDistance = FindRootDistance(root.left, x, y);
Distance RightDistance = FindRootDistance(root.right, x, y);
if ((LeftDistance.xExists && RightDistance.yExists) || (LeftDistance.xExists && RightDistance.yExists))
return new Distance(LeftDistance.distance + RightDistance.distance, true, true);
else if (LeftDistance.xExists && LeftDistance.yExists)
return LeftDistance;
else if (RightDistance.xExists && LeftDistance.yExists)
return RightDistance;
else if (LeftDistance.xExists && root.val == y)
{
LeftDistance.yExists = true;
return LeftDistance;
}
else if (LeftDistance.yExists && root.val == x)
{
LeftDistance.xExists = true;
return LeftDistance;
}
else if (RightDistance.xExists && root.val == y)
{
RightDistance.yExists = true;
return RightDistance;
}
else if (RightDistance.yExists && root.val == x)
{
RightDistance.xExists = true;
return RightDistance;
}
else if (LeftDistance.xExists || LeftDistance.yExists)
{
LeftDistance.distance += 1;
return LeftDistance;
}
else if (RightDistance.xExists || RightDistance.yExists)
{
RightDistance.distance += 1;
return RightDistance;
}
else if (root.val == x)
return new Distance(1, true, false);
else if (root.val == y)
return new Distance(1, false, true);
else
{
return new Distance(0, false, false);
}
}
public class Distance
{
public int distance;
public bool xExists;
public bool yExists;
public Distance(int d, bool bx, bool by)
{
this.distance = d;
this.xExists = bx;
this.yExists = by;
}
}
public Distance FindRootDistance(TreeNode root, int x, int y)
{
if (root == null)
return new Distance(0, false, false);
if (x == y)
return new Distance(0, true, true);
Distance LeftDistance = FindRootDistance(root.left, x, y);
Distance RightDistance = FindRootDistance(root.right, x, y);
if ((LeftDistance.xExists && RightDistance.yExists) || (LeftDistance.xExists && RightDistance.yExists))
return new Distance(LeftDistance.distance + RightDistance.distance, true, true);
else if (LeftDistance.xExists && LeftDistance.yExists)
return LeftDistance;
else if (RightDistance.xExists && LeftDistance.yExists)
return RightDistance;
else if (LeftDistance.xExists && root.val == y)
{
LeftDistance.yExists = true;
return LeftDistance;
}
else if (LeftDistance.yExists && root.val == x)
{
LeftDistance.xExists = true;
return LeftDistance;
}
else if (RightDistance.xExists && root.val == y)
{
RightDistance.yExists = true;
return RightDistance;
}
else if (RightDistance.yExists && root.val == x)
{
RightDistance.xExists = true;
return RightDistance;
}
else if (LeftDistance.xExists || LeftDistance.yExists)
{
LeftDistance.distance += 1;
return LeftDistance;
}
else if (RightDistance.xExists || RightDistance.yExists)
{
RightDistance.distance += 1;
return RightDistance;
}
else if (root.val == x)
return new Distance(1, true, false);
else if (root.val == y)
return new Distance(1, false, true);
else
{
return new Distance(0, false, false);
}
}
public class Distance
{
public int distance;
public bool xExists;
public bool yExists;
public Distance(int d, bool bx, bool by)
{
this.distance = d;
this.xExists = bx;
this.yExists = by;
}
}
public Distance FindRootDistance(TreeNode root, int x, int y)
{
if (root == null)
return new Distance(0, false, false);
if (x == y)
return new Distance(0, true, true);
Distance LeftDistance = FindRootDistance(root.left, x, y);
Distance RightDistance = FindRootDistance(root.right, x, y);
if ((LeftDistance.xExists && RightDistance.yExists) || (LeftDistance.xExists && RightDistance.yExists))
return new Distance(LeftDistance.distance + RightDistance.distance, true, true);
else if (LeftDistance.xExists && LeftDistance.yExists)
return LeftDistance;
else if (RightDistance.xExists && LeftDistance.yExists)
return RightDistance;
else if (LeftDistance.xExists && root.val == y)
{
LeftDistance.yExists = true;
return LeftDistance;
}
else if (LeftDistance.yExists && root.val == x)
{
LeftDistance.xExists = true;
return LeftDistance;
}
else if (RightDistance.xExists && root.val == y)
{
RightDistance.yExists = true;
return RightDistance;
}
else if (RightDistance.yExists && root.val == x)
{
RightDistance.xExists = true;
return RightDistance;
}
else if (LeftDistance.xExists || LeftDistance.yExists)
{
LeftDistance.distance += 1;
return LeftDistance;
}
else if (RightDistance.xExists || RightDistance.yExists)
{
RightDistance.distance += 1;
return RightDistance;
}
else if (root.val == x)
return new Distance(1, true, false);
else if (root.val == y)
return new Distance(1, false, true);
else
{
return new Distance(0, false, false);
}
}
- Kapil July 27, 2017