## Google Interview Question for Software Engineers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 vote

Level tree traversal and check if you can find x and y in current level in specified order.
Could you tell more for what position is this question - SDE1, SDE2 ...?

Comment hidden because of low score. Click to expand.
2
of 2 vote

C++, DFS, O(n log n)

``````struct Node {
int x;
int y;
Node* child;
Node* sibling;
Node(int vx, int vy): child(NULL), sibling(NULL) {
x = vx;
y = vy;
}
};

struct WorkingNode {
Node* node;
int depth;
int state;
};

bool find(Node* root, int x, int y) {
stack<WorkingNode> stk;
WorkingNode w;
set<int> xs, ys;

w.node = root;
w.depth = 0;
w.state = 0;
stk.push(w);

while (!stk.empty()) {
w = stk.top();
stk.pop();
if (w.node == NULL) continue;

if (w.state == 0) {
if (w.node->x == x) {
if (ys.find(w.depth) != ys.end()) return true;
xs.insert(w.depth);
}
if (w.node->y == y) {
if (xs.find(w.depth) != xs.end()) return true;
ys.insert(w.depth);
}
w.state = 1;
stk.push(w);
w.node = w.node->child;
w.depth++;
w.state = 0;
stk.push(w);
} else {
w.node = w.node->sibling;
w.state = 0;
stk.push(w);
}
}

return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Also is it true, that first value x is always less or equal than second value y in each node?
Is there ascending arrangement in each level by first value . For ex. (5,15), (30,70), (80,110) , or just the example is provided in this way?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import lombok.RequiredArgsConstructor;
import lombok.Value;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Set;
import java.util.stream.Collectors;

import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.MatcherAssert.assertThat;

public class Tree001 {

@Value // Lombok: produce all getters
@RequiredArgsConstructor
// Lombok: produce Node(x,y,Collection<Node>)
class Node {
public Node(int x, int y) {
this(x, y, new ArrayList<>());
}

private final int x, y;
private final Collection<Node> nodes;
}

public boolean find(Node root, int x, int y) {
return find(Arrays.asList(root), x, y);
}

public boolean find(Collection<Node> nodes, int x, int y) {
if (nodes.isEmpty()) return false;
Set<Integer> xSet = nodes.stream().map(Node::getX).collect(Collectors.toSet());
Set<Integer> ySet = nodes.stream().map(Node::getY).collect(Collectors.toSet());
if (xSet.contains(x) && ySet.contains(y)) return true;
return find(nodes.stream().flatMap(n -> n.getNodes().stream()).collect(Collectors.toList()), x, y);
}

@Test
public void test() {
Node root = new Node(1, 120, Arrays.asList(
new Node(5, 15, Arrays.asList(
new Node(35, 40),
new Node(45, 50),
new Node(55, 65))),
new Node(30, 70, Arrays.asList(
new Node(90, 100))),
new Node(80, 110)));
assertThat(find(root, 45, 100), is(Boolean.TRUE));
assertThat(find(root, 30, 100), is(Boolean.FALSE));
assertThat(find(root, 30, 70), is(Boolean.TRUE));
assertThat(find(root, 70, 30), is(Boolean.FALSE));
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import lombok.RequiredArgsConstructor;
import lombok.Value;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Set;
import java.util.stream.Collectors;

import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.MatcherAssert.assertThat;

public class Tree001 {

@Value // Lombok: produce all getters
@RequiredArgsConstructor
// Lombok: produce Node(x,y,Collection<Node>)
class Node {
public Node(int x, int y) {
this(x, y, new ArrayList<>());
}

private final int x, y;
private final Collection<Node> nodes;
}

public boolean find(Node root, int x, int y) {
return find(Arrays.asList(root), x, y);
}

public boolean find(Collection<Node> nodes, int x, int y) {
if (nodes.isEmpty()) return false;
Set<Integer> xSet = nodes.stream().map(Node::getX).collect(Collectors.toSet());
Set<Integer> ySet = nodes.stream().map(Node::getY).collect(Collectors.toSet());
if (xSet.contains(x) && ySet.contains(y)) return true;
return find(nodes.stream().flatMap(n -> n.getNodes().stream()).collect(Collectors.toList()), x, y);
}

@Test
public void test() {
Node root = new Node(1, 120, Arrays.asList(
new Node(5, 15, Arrays.asList(
new Node(35, 40),
new Node(45, 50),
new Node(55, 65))),
new Node(30, 70, Arrays.asList(
new Node(90, 100))),
new Node(80, 110)));
assertThat(find(root, 45, 100), is(Boolean.TRUE));
assertThat(find(root, 30, 100), is(Boolean.FALSE));
assertThat(find(root, 30, 70), is(Boolean.TRUE));
assertThat(find(root, 70, 30), is(Boolean.FALSE));
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

BFS Java Elegant solution

``````import lombok.RequiredArgsConstructor;
import lombok.Value;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Set;
import java.util.stream.Collectors;

import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.MatcherAssert.assertThat;

public class Tree001 {

@Value // Lombok: produce all getters
@RequiredArgsConstructor
// Lombok: produce Node(x,y,Collection<Node>)
class Node {
public Node(int x, int y) {
this(x, y, new ArrayList<>());
}

private final int x, y;
private final Collection<Node> nodes;
}

public boolean find(Node root, int x, int y) {
return find(Arrays.asList(root), x, y);
}

public boolean find(Collection<Node> nodes, int x, int y) {
if (nodes.isEmpty()) return false;
Set<Integer> xSet = nodes.stream().map(Node::getX).collect(Collectors.toSet());
Set<Integer> ySet = nodes.stream().map(Node::getY).collect(Collectors.toSet());
if (xSet.contains(x) && ySet.contains(y)) return true;
return find(nodes.stream().flatMap(n -> n.getNodes().stream()).collect(Collectors.toList()), x, y);
}

@Test
public void test() {
Node root = new Node(1, 120, Arrays.asList(
new Node(5, 15, Arrays.asList(
new Node(35, 40),
new Node(45, 50),
new Node(55, 65))),
new Node(30, 70, Arrays.asList(
new Node(90, 100))),
new Node(80, 110)));
assertThat(find(root, 45, 100), is(Boolean.TRUE));
assertThat(find(root, 30, 100), is(Boolean.FALSE));
assertThat(find(root, 30, 70), is(Boolean.TRUE));
assertThat(find(root, 70, 30), is(Boolean.FALSE));
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class Node
{
int x;
int y;
Node[]children;
}

public boolean find(Node root, int x, int y)
{
if(root == null)
{
return false;
}

int queueCount = 1;

while(childQueue.peek()!= null)
{
bool xFound = false;
bool yFound = false;
int newQueueCount = 0;
for(int i = 0; i< queueCount; i++)
{
Node n = childQueue.poll();
if(!xFound)
{
xFound = (n.x == x);
}
else if(!yFound)
{
yFound = (n.y == y);
}
else if(xFound && yFound)
{
return true;
}

for(int j=0; j<n.children.length; j++)
{
newQueueCount++;
}
}
queueCount = newQueueCount;
}
return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class TreeLevelPrint
{
treeNode root;
int[] left, right; // vaules which are left child are stored in left and right child in right level wise
int lid, rid;
public TreeLevelPrint()
{
treeNode root = null;
MinDiffBst m = new MinDiffBst(ref  root);// this creates the tree and returns the root node in rrot variable
this.root = root;
printOrder(root);
}
void printOrder(treeNode root)
{
int i = 0;
int level;
int leftVal, rightVal;
int hiegt = height(root);
Console.WriteLine("Enter left Val :");
leftVal = Int32.Parse(Console.ReadLine());  // value of node which is to found as left child
Console.WriteLine("Enter right Val :");
rightVal = Int32.Parse(Console.ReadLine()); // value of node which is to found as right child
//This loop Traverses the elements of tree level wise
for (level  = 1 ; level <= hiegt ; level++)
{
left = new int[(int)Math.Pow(2,level  - 2)];
right = new int[(int)Math.Pow(2, level - 2)];
while (i < left.Length)
{
left[i] = 0;
i++;
}
i = 0;
while (i < right.Length)
{
right[i] = 0;
i++;
}
lid = 0;
rid = 0;
printLevel(root, level,"");
if (level > 1)
{
Boolean flag = false;
for (int j = 0; j < left.Length; j++)
{
if (left[j] == leftVal)
flag = true;
}
if (flag == true)
{
flag = false;
for (int j = 0; j < left.Length; j++)
{
if (right [j] == rightVal )
flag = true;
}
if (flag == true)
{
Console.WriteLine("Found at Level " + level);
break;
}
else if (level == hiegt)
}
else if (level == hiegt )
}
}
}
void printLevel(treeNode root, int level, string side)
{
if (root == null)
return ;
if (level == 1)
{
if (side == "L")
{
left[lid] = root.value;
lid++;
}
else if (side =="R")
{
right[rid ] = root.value;
rid++;
}
}
else if (level > 1)
{
printLevel(root.left, level - 1,"L");
printLevel(root.right, level - 1,"R");
}
}
int height(treeNode root)
{
if (root == null)
return 0;
else
{
int lht = height(root.left );
int rht = height(root.right);
if (lht > rht)
return lht + 1;
else
return rht + 1;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class treeNode
{
public int value = 0;
public treeNode left, right;
}
class TreeLevelPrint
{
treeNode root;
int[] left, right; // vaules which are left child are stored in left and right child in right (level wise)
int lid, rid;
public TreeLevelPrint()
{
treeNode root = null;
MinDiffBst m = new MinDiffBst(ref  root);// this creates the tree and returns the root node in rrot variable
this.root = root;
printOrder(root);
}
void printOrder(treeNode root)
{
int i = 0;
int level;
int leftVal, rightVal;
int hiegt = height(root);
Console.WriteLine("Enter left Val :");
leftVal = Int32.Parse(Console.ReadLine());  // value of node which is to found as left child
Console.WriteLine("Enter right Val :");
rightVal = Int32.Parse(Console.ReadLine()); // value of node which is to found as right child
//This loop Traverses the elements of tree level wise
for (level  = 1 ; level <= hiegt ; level++)
{
left = new int[(int)Math.Pow(2,level  - 2)];
right = new int[(int)Math.Pow(2, level - 2)];
while (i < left.Length)
{
left[i] = 0;
i++;
}
i = 0;
while (i < right.Length)
{
right[i] = 0;
i++;
}
lid = 0;
rid = 0;
printLevel(root, level,"");
if (level > 1)
{
Boolean flag = false;
for (int j = 0; j < left.Length; j++)
{
if (left[j] == leftVal)
flag = true;
}
if (flag == true)
{
flag = false;
for (int j = 0; j < left.Length; j++)
{
if (right [j] == rightVal )
flag = true;
}
if (flag == true)
{
Console.WriteLine("Found at Level " + level);
break;
}
else if (level == hiegt)
}
else if (level == hiegt )
}
}
}
void printLevel(treeNode root, int level, string side)
{
if (root == null)
return ;
if (level == 1)
{
if (side == "L")
{
left[lid] = root.value;
lid++;
}
else if (side =="R")
{
right[rid ] = root.value;
rid++;
}
}
else if (level > 1)
{
printLevel(root.left, level - 1,"L");
printLevel(root.right, level - 1,"R");
}
}
int height(treeNode root)
{
if (root == null)
return 0;
else
{
int lht = height(root.left );
int rht = height(root.right);
if (lht > rht)
return lht + 1;
else
return rht + 1;
}
}
static void Main(string[] args)
{
new TreeLevelPrint();
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

use bfs! Space O(width), time O(n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Breath Search Traversal, without recursion. C# implementation

``````public bool Find(TreeNode root, int x, int y)
{
if (root == null)
return false;

var current = new List<TreeNode>();

while (current.Count > 0)
{
bool foundX = false;
bool foundY = false;
var next = new List<TreeNode>();

foreach(var node in current)
{
foundX |= (node.X == x);
foundY |= (node.Y == y);
if (foundX && foundY)
return true;

foreach (var child in node.Child)
}

current = next;
}

return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import collections
class TreeNode(object):
def __init__(self,x,y):
self.x = x
self.y = y
self.left = None
self.right = None
class Solution(object):
def sameLevel(self,root,x,y):
if not root:
return False
queue = collections.deque([(root,0)])
level = 0
sameLevel = [False,False]
while queue:
node = queue.popleft()
node[1]!=level:
level+=1
sameLevel = [False,False]
if node[0].left:
queue.append((node[0].left,level+1))
if node[0].right:
queue.append((node[0].right,level+1))
if node[0].x == x:
sameLevel[0] = True
if node[0].y == y:
sameLevel[1] = True
if sameLevel == [True,True]:
return True
return False``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class Tree:
def __init__(data, children = []):
this.data = data
this.child = children

def pair_tree(root, x, y):
if root:
stack = [root]
while (stack is not []):
next_stack = []
found_x, found_y = False, False
for node in stack:
new_stack += node.children
found_x = node.x == x or found_x
found_y = node.y == y or found_y
if (found_x and found_y):
return True
stack = new_stack
return False``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>
#include <queue>

using namespace std;

class node{

public :

int data;
node* left;
node* right;

node(int data, node* left, node* right){
this->data = data;
this->left = left;
this->right = right;
}

};

class tree{

public :

node* insert(int x, node* tree){
if(tree == NULL){
tree = new node(x, NULL, NULL);
}else if(tree->data > x){
tree->left = insert(x, tree->left);
}else if(tree->data < x){
tree->right = insert(x, tree->right);
}

return tree;
}

bool find1(node* root, int x, int y){
if(root == NULL){
return false;
}

if(root->left == NULL && root->right == NULL){
return true;
}

queue<node*> q;

q.push(root);

int length;

while(true){

length = q.size();
if(length == 0){
break;
}

int i=0;
bool found1 = false, found2 = false;
while(i < length){
node* curr = q.front();
if(curr->data == x){
found1 = true;
}
if(curr->data == y){
found2 = true;
}
if(curr->left != NULL){
q.push(curr->left);
}

if(curr->right != NULL){
q.push(curr->right);
}
q.pop();
i++;
}

if(found1 && found2){
return true;
}

}

return false;
}

};

int main()
{
node* root;
tree t;
root = t.insert(6, root);
root = t.insert(3, root);
root = t.insert(13, root);
root = t.insert(10, root);

cout<<t.find1(root, 6, 13)<<endl;

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

My method is based on BFS using Queue. It is based on calculating the number of nodes in the next level, decrementing it and we detect that the level is changed once the currentLevelCounter reaches 0.

``````public boolean find(Node n,int x, int y){
boolean found = false;
int currentLevelCount=1;
int nextLevelCount=0;
Queue toBeDiscovered=new Queue();
toBeDiscovered.enqueue(n);
ArrayList<Node> levelNodes=new ArrayList<Node>();

while (toBeDiscovered.first!=null){

Node current=toBeDiscovered.dequeue();
currentLevelCount--;
nextLevelCount=nextLevelCount+current.children.size();
for (int i=0;i<current.children.size();i++){
toBeDiscovered.enqueue(current.children.get(i));
}

if (currentLevelCount==0){
found=false;
currentLevelCount=nextLevelCount;
nextLevelCount=0;

for (int i=0;i<levelNodes.size();i++){

if (levelNodes.get(i).x==x)
found=true;
if (levelNodes.get(i).y==y && found==true)
return true;
}
levelNodes=new ArrayList<Node>();
}
}
return false;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Find height of each node to be found from the root. If height is same of both the nodes then return true.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class Node(object):
def __init__(self, parent, children, x, y):
self.parent = parent
self.children = children
self.x = x
self.y = y

def find(root, x, y):
if not root.children:
return False
children = root.children
while children:
if scan_level(children, x, y):
return True
new_children = []
for node in children:
new_children += node.children
children = new_children
return False

def scan_level(nodes, x, y):
has_x, has_y = False, False
for node in nodes:
if node.x == x:
has_x = True
if node.y == y:
has_y = True
if has_x and has_y:
return True
return False

if __name__ == "__main__":
root = Node(None, None, 1, 120)
n10 = Node(root, None, 5, 15)
n11 = Node(root, None, 30, 70)
n12 = Node(root, [], 80, 110)
n20 = Node(n10, [], 35, 40)
n21 = Node(n10, [], 45, 50)
n22 = Node(n10, [], 55, 65)
n23 = Node(n11, [], 90, 100)

root.children = [n10, n11, n12]
n10.children = [n20, n21, n22]
n11.children = [n23]

assert find(root, 45, 100) == True
assert find(root, 30, 100) == False
assert find(root, 30, 70) == True
assert find(root, 70, 30) == False``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

with JavaScript

``````find(root, x, y)
{
root.level = 0;
var queue = [root];

var currentLevel = -1;
var foundX, foundY;
do
{
var node = queue.shift();
if (node.level > currentLevel) {
currentLevel = node.level;
foundX = false;
foundY = false;
}
if (node.x === x) {
foundX = true;
}
if (node.y === y) {
foundY = true;
}
if (foundX && foundY) {
return true;
}

if (node.left) {
node.right.level = node.level + 1;
queue.push(node.left);
}

if (node.right) {
node.right.level = node.level + 1;
queue.push(node.right)
}
} while (queue.length > 0)

return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````find(root, x, y)
{
root.level = 0;
var queue = [root];

var currentLevel = -1;
var foundX, foundY;
do
{
var node = queue.shift();
if (node.level > currentLevel) {
currentLevel = node.level;
foundX = false;
foundY = false;
}
if (node.x === x) {
foundX = true;
}
if (node.y === y) {
foundY = true;
}
if (foundX && foundY) {
return true;
}

if (node.left) {
node.right.level = node.level + 1;
queue.push(node.left);
}

if (node.right) {
node.right.level = node.level + 1;
queue.push(node.right)
}
} while (queue.length > 0)

return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````function find(root, x, y)
{
root.level = 0;
var queue = [root];

var currentLevel = -1;
var foundX, foundY;
do
{
var node = queue.shift();
if (node.level > currentLevel) {
currentLevel = node.level;
foundX = false;
foundY = false;
}
if (node.x === x) {
foundX = true;
}
if (node.y === y) {
foundY = true;
}
if (foundX && foundY) {
return true;
}

if (node.left) {
node.right.level = node.level + 1;
queue.push(node.left);
}

if (node.right) {
node.right.level = node.level + 1;
queue.push(node.right)
}
} while (queue.length > 0)

return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class SolutionSameLevelXYTree {

public static boolean find(Node root, int x, int y) {
Map<Integer, Integer> allLevelsX = new HashMap<>();
Map<Integer, Integer> allLevelsY = new HashMap<>();

findAllLevelsOccurenceOfVal(root, x, 0, true, allLevelsX);
findAllLevelsOccurenceOfVal(root, y, 0, false, allLevelsY);

if (allLevelsX.isEmpty() || allLevelsY.isEmpty()) {
return false;
}

for (Entry<Integer, Integer> lX: allLevelsX.entrySet()) {
if (allLevelsY.get(lX.getKey()) != null) {
return true;
}
}

return false;
}

public static void findAllLevelsOccurenceOfVal(Node root, int v, int l, boolean isX, Map<Integer, Integer> levelCount) {
if (root == null) {
return;
}

if (isX && root.x == v || !isX && root.y == v) {
if (levelCount.get(l) == null) {
levelCount.put(l, 1);
} else {
int count = levelCount.get(l);
levelCount.put(l, count + 1);
}
}

if (root.children != null) {
for (Node n : root.children) {
findAllLevelsOccurenceOfVal(n, v, l+1, isX, levelCount);
}
}
}

public static void testSolution() {
Node n1 = new Node(1, 120);
Node n2 = new Node(5, 15);
Node n3 = new Node(30, 70);
Node n4 = new Node(80, 110);
Node n5 = new Node(35, 40);
Node n6 = new Node(45, 50);
Node n7 = new Node(55, 65);
Node n8 = new Node(90, 100);

List<Node> n1List = new ArrayList<>();
n1.children = n1List;

List<Node> n2List = new ArrayList<>();
n2.children = n2List;

List<Node> n3List = new ArrayList<>();
n3.children = n3List;

List<Node> n4List = new ArrayList<>();
n4.children = n4List;

System.out.println(find(n1, 45, 100));
System.out.println(find(n1, 30, 100));
System.out.println(find(n1, 30, 70));
System.out.println(find(n1, 70, 30));
}
}

class Node {
int x;
int y;

List<Node> children;

public Node(int x, int y) {
super();
this.x = x;
this.y = y;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
* Created by nileshagrawal on 5/22/16.
* BFS on the queue elements
*/

``````class TreeNode{
private int  x;
private int  y;
private List<TreeNode> childNodeList;

public TreeNode(int x, int y, List<TreeNode> childNodeList) {
this.x = x;
this.y = y;
this.childNodeList = childNodeList;
}

public int getX() {
return x;
}

public void setX(int x) {
this.x = x;
}

public int getY() {
return y;
}

public void setY(int y) {
this.y = y;
}

public List<TreeNode> getChildNodeList() {
return childNodeList;
}

public void setChildNodeList(List<TreeNode> childNodeList) {
this.childNodeList = childNodeList;
}

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;

TreeNode treeNode = (TreeNode) o;

if (x != treeNode.x) return false;
if (y != treeNode.y) return false;
return childNodeList != null ? childNodeList.equals(treeNode.childNodeList) : treeNode.childNodeList == null;

}

@Override
public int hashCode() {
int result = x;
result = 31 * result + y;
result = 31 * result + (childNodeList != null ? childNodeList.hashCode() : 0);
return result;
}
}

public class FindingElementWithTwoValues {

public boolean findTheValue(TreeNode root,TreeNode givenNode){

if(root == null){
return false;
}
boolean leftFound = false;
boolean rightFound = false;
while (!queue.isEmpty()){

TreeNode tempNode = queue.poll();
if(tempNode == null){
System.out.print("end of level.");
if(leftFound && rightFound){
return true;
}else{
leftFound = false;
rightFound = false;
}
}else{

for(TreeNode childNode:tempNode.getChildNodeList()){
if(childNode!=null){
if(childNode.getX() == givenNode.getX()){
leftFound = true;
}

if(childNode.getY() == givenNode.getY()){
rightFound = true;
}
}
}

}
}
return false;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package test;

Node root;
int size = 0;

private class Node {

int key;
String name;

Node leftChild;
Node rightChild;

Node(int key, String name) {

this.key = key;
this.name = name;

}

public String toString() {

return name + " has the key " + key;

}

}

public void addNode(int key, String name){

Node node = root;
Node newNode = new Node(key, name);

// If there is no root this becomes root

if (root == null) {

root = newNode;
size++;

} else {

while (true){

if (node.key > newNode.key){

if (node.leftChild !=null){

node = node.leftChild;

}else{

node.leftChild = newNode;
size++;
return;
}

}else{

if (node.rightChild !=null){

node = node.rightChild;

}
else{

node.rightChild = newNode;
size++;
return;
}

}

}

}

}

public boolean FindDeephNodesIfExists(Node root, int keyOne, int keyTwo){

int nodeOne = findTwoNodes(root, keyOne, true);
int nodeTwo = findTwoNodes(root, keyTwo, false);

return nodeOne==nodeTwo?true:false;
}

public int findTwoNodes (Node root, int key, boolean isLeftNodeToFind) {

Node node = root;
int depth = -1;
boolean isRigth = false;

if (root == null) {

return -1;

} else {

while (node.key != key){

if (node.key > key){

node = node.leftChild;
isRigth = false;
}else{
node = node.rightChild;
isRigth = true;

}

if (node == null)
return -1;

++depth;
}

if (isRigth && isLeftNodeToFind){

depth = -1;

}

return ++depth;
}

}

public Node findNode(int key) {

Node node = root;

if (root == null) {

return null;

} else {

while (node.key != key){

if (node.key > key){

node = node.leftChild;

}else{
node = node.rightChild;

}

if (node == null)
return null;
}

return node;
}

}

public static void main(String[] args) {

// System.out.println(theTree.findNode(75));

Node rootForSearch =  theTree.findNode(50);

System.out.println(theTree.FindDeephNodesIfExists(rootForSearch, 25, 75));

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is an Objective-C solution, basically, iterate by level using a queue and store in a dictionary the level of the X and Y value found and then check if those has the same level

``````-(BOOL)find:(TreeNode *)root andX:(int)x andY:(int)y{

if(root == nil){

return false;
}

NSMutableArray *queue = [NSMutableArray new];
NSMutableDictionary *dic = [NSMutableDictionary new];

while ([queue count] > 0) {

root = [queue objectAtIndex:0];
[queue removeObjectAtIndex:0];
NSLog(@"\n\n%i\nLEVEL: %i\n", root.value, root.level);

if(root.value == x){

[dic setObject:[NSNumber numberWithInt:root.level] forKey:@"X"];
}

if(root.value == y){

[dic setObject:[NSNumber numberWithInt:root.level] forKey:@"Y"];
}

if([dic count] == 2){

if([[dic objectForKey:@"X"] intValue] == [[dic objectForKey:@"Y"] intValue]){

return true;
}

}

if(root.left != nil){

root.left.level = root.level + 1;
}

if(root.rigth != nil){

root.rigth.level = root.level + 1;
}
}

return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is an Objective-C solution, basically, iterate by level using a queue and store in a dictionary the level of the X and Y value found and then check if those are in the same level

``````@interface TreeNode : NSObject

@property (nonatomic, assign) int value;

@property (nonatomic, strong) TreeNode *left;

@property (nonatomic, strong) TreeNode *rigth;

@property (nonatomic, assign) int level;

-(instancetype)initWithValue:(int)value;

@end

-(BOOL)find:(TreeNode *)root andX:(int)x andY:(int)y{

if(root == nil){

return false;
}

NSMutableArray *queue = [NSMutableArray new];
NSMutableDictionary *dic = [NSMutableDictionary new];

while ([queue count] > 0) {

root = [queue objectAtIndex:0];
[queue removeObjectAtIndex:0];
NSLog(@"\n\n%i\nLEVEL: %i\n", root.value, root.level);

if(root.value == x){

[dic setObject:[NSNumber numberWithInt:root.level] forKey:@"X"];
}

if(root.value == y){

[dic setObject:[NSNumber numberWithInt:root.level] forKey:@"Y"];
}

if([dic count] == 2){

if([[dic objectForKey:@"X"] intValue] == [[dic objectForKey:@"Y"] intValue]){

return true;
}

}

if(root.left != nil){

root.left.level = root.level + 1;
}

if(root.rigth != nil){

root.rigth.level = root.level + 1;
}
}

return false;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.