## Google Interview Question for Software Engineer / Developers

• 0

Country: United States

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

for inorder traversal:
=> if k-left == 1: n is curr node
=> else if k > left+1 : n = n.right, k = k-left-1
=> else : n = n.left

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

I don't understand what does n mean? Can you explain more about the question and answer?

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

Adi's solution seems to be correct with a few examples I tried.
'n' is the current node, the logic should start with n as the root node.

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

``````Did you mean a BinaryTree with n number of nodes and find k'th node while traversing in-order?
Or
You are given a node "n" and find k'th element under that subtree.``````

I am sure it's not this trivial as your question sounds.

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

``````//Java Version without recursion
Node currentNode = rootNode;
int k = 1;
int currentK = k;
while (currentNode != null) {
int currentNodeRank = currentNode.count;
if (currentNode.left != null) {
currentNodeRank = currentNode.left.count + 1;
}

else if (currentNode.right != null) {
currentNodeRank = 1;
}
//System.out.format("nodeRank %s for node %s with current K %d\n",currentNodeRank,currentNode.value,currentK );
if (currentK == currentNodeRank) {
System.out.println("found this " + currentNode.value);
System.exit(1);
}
if(currentK < currentNodeRank) {
currentNode = currentNode.left;
continue;
}
else {
currentK = currentK - currentNodeRank;
currentNode = currentNode.right;
}
}``````

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

``````public Node findKthNode(Node root, int number) {
if (root == null) {
return null; //or throw an exception
}
int leftRange = 0;
int rightRange = root.totalElements;

if (number > rightRange) {
return null; //or throw an exception
}
Node current = root;
while (current != null) {
int currentTotal = current.totalElements;
Node left = current.left;
int leftTotal = left == null ? 0 : left.totalElements;

int currentPosition = leftRange + leftTotal + 1;
if (currentPosition == number) { //found it
return current;
} else if (currentPosition < number) { //go right
leftRange = currentPosition;
current = current.right;
} else if (currentPosition > number) { //go left
rightRange = currentPosition;
current = current.left;
}
}

return null; //not possible unless nodes' totalElements corrupt
}``````

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

``````public Node findInOrder(Node n, int k){
if(n.childno-1 == k)
return n;
if(n.childLeft != null && n.childLeft.childno >= k-1)
return findInOrder(n.childLeft, k);
else
return findInOrder(n.childRight, k);
}``````

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

int inorder(struct node *tree1)
{

if(tree1!=NULL)
{
inorder(tree1->left);
if(count==5) where count is a global variable
return(tree1->no);
else
{
count++;
printf("%d ",tree1->no);
}
inorder(tree1->right);
}
}

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

``````class InOrderTraversalFindK
{
public class Node
{
public Node Left;
public Node Right;
public int Count;
}

public static Node findK(Node root, int k)
{
if (k > root.Count) return null;
if (k == root.Count) return root;
if (k <= root.Left.Count)
{
return findK(root.Left, k);
}
else
{
return findK(root.Right, k - root.Left.Count);
}
}

public static Node findKNonRecursive(Node root, int k)
{
if (k > root.Count) return null;

Node curNode = root;
while (curNode!=null)
{
if (k == curNode.Count) return curNode;
if (k <= curNode.Left.Count)
{
curNode = curNode.Left;
}
else
{
k -= curNode.Left.Count;
curNode = curNode.Right;
}
}
return null;
}
}``````

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

I don't think findk is right. Consider a node with one left and one right. root.count == 3. Your code will return root in this case, but you want it to return root.right, since its in order traversal.

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

``````public Node kthRecurse(Node root, int k) {
int lSize = (root.left == null) ? 0 : root.left.getCount();
if (k <= lSize) return kthRecursive(root.left, k);
if (k == 1) return root;
return kthRecursive(root.right, k - 1 - lSize);
}

public Node kthIterative(Node root, int k) {
Node cur = root;
int i = k;
while (true) {
int lSize = (cur.left == null) ? 0 : cur.left.getCount();
if (k <= lSize) {
cur = cur.left;
continue;
}
if (k == 1) break;
cur = cur.right;
i = i - ls - 1;
}
return cur;
}``````

Something like this could probably work.

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

I think we can just maintain a current node and compare the number of its left child and k, then move the current node. Here is my implementation and test cases.

``````#include <iostream>
using namespace std;

struct TreeNode{
int num, no;//the amount of nodes and the id
TreeNode *left, *right;
TreeNode(int _num, int _no):num(_num), no(_no), left(NULL), right(NULL){}
};

TreeNode* solve(TreeNode *root, int k){
if(root == NULL || root->num<k || k<=0)   return NULL;
TreeNode *cur = root;
while(k > 0){
int lnum = cur->left?cur->left->num:0;
int rnum = cur->num-lnum-1;
if(k == lnum+1) return cur;
else if(k<=lnum){
cur = cur->left;
}else{
cur = cur->right;
k -= lnum+1;
}
}
return NULL;
}

int main(){
TreeNode *t1 = new TreeNode(10, 1);
TreeNode *t2 = new TreeNode(4, 2);
TreeNode *t3 = new TreeNode(5, 3);
TreeNode *t4 = new TreeNode(3, 4);
TreeNode *t5 = new TreeNode(2, 5);
TreeNode *t6 = new TreeNode(2, 6);
TreeNode *t7 = new TreeNode(1, 7);
TreeNode *t8 = new TreeNode(1, 8);
TreeNode *t9 = new TreeNode(1, 9);
TreeNode *t10 = new TreeNode(1, 10);
t1->left = t2;
t1->right = t3;
t2->left = t4;
t3->left = t5;
t3->right = t6;
t4->left = t7;
t4->right = t8;
t5->left = t9;
t6->right = t10;
cout<<solve(t1, 8)->no<<endl; //3
cout<<solve(t1, 5)->no<<endl; //1
cout<<solve(t1, 3)->no<<endl; //8
cout<<solve(t2, 3)->no<<endl; //8
cout<<solve(t3, 1)->no<<endl; //9
}

/*
10
/ \
4  5
/\  /\
3 0 2 2
/\  /\ /\
1 1 1 00 1
*/``````

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

``````public Node findKth(Node n, int k) {
// first check if the tree has k node
if (n.getNum() < k) { return null; }

// otherwise, the kth is in this tree.
if (n.left.getNum() >= k) {
// check if kth is in left subtree
return findKth(n.left, k);
} else if (n.left.getNum() = k-1) {
// see if our root is actually the kth
return n;
} else {
// then it has to be in the right subtree
// need to minus the number of left subtree and the root first.
int minus = n.left.getNum() + 1;
return findKth(n.right, k-minus);
}
}

public Node findKthNonRec(Node n, int k) {
// first check if the tree has kth.
if (n.getNum() < k) { return null; }

int count = k;
Node current = n;
while (current.left.getNum() != k-1) {// while current is not the kth
if (current.left.getNum >= k) {// see if kth in left subtree
current = current.left;
} else {// kth is in right subtree
count = count - 1 - current.left.getNum();
current = current.right;
}
}
return current;
}``````

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

``````public class Node {
int value;
Node left;
Node right;
int count;
}

public Node kthInOrder (Node a, int k) {
//return the kth node of an in order traversal
Node curr = a;
int n_visited = 0; //visit the root
while (n_visited <= k) {
int n_left = curr.left==null ? 0 : curr.left.count;
if (k == n_visited + n_left) return curr;
//visit more nodes
if (n_visited + n_left < k) {
//go right
n_visited += curr.n_left;
curr = curr.right;
} else curr = curr.left;
}
return null;
}``````

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

``````struct CTreeNode{
int count;
int val;
CTreeNode *left;
CTreeNode *right;
CTreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

CTreeNode *findNodeInOrder(CTreeNode *root, int k){
if(root==nullptr || k<0 || k>root->count) return nullptr;
if(k==root->count){
if(root->right==nullptr)
return root;
return findNodeInOrder(root->right, root->count);
}
if(root->left!=nullptr){
if(root->left->count>=k)
return findNodeInOrder(root->left, k);
else if(root->left->count==k-1)
return root;
else
return findNodeInOrder(root->right, k-root->left->count-1);

}
return findNodeInOrder(root->right, k);
}``````

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

``````public Node FindKthRecursive(Node n, int k)
{
if (k > n.data)
return null;

while (n.left != null && n.left.data >= k)
n = n.left;

if (n.left != null)
k -= n.left.data;

if (--k == 0)
return n;
else
return FindKthRecursive(n.right, k);
}

public Node FindKthIterative(Node n, int k)
{
if (k > n.data)
return null;

while (true)
{
while (n.left != null && n.left.data >= k)
n = n.left;

if (n.left != null)
k -= n.left.data;

if (--k == 0)
return n;

n = n.right;
}
}``````

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

``````Tree findkthNode(Tree node, int k)
{
int parent=0;
//

while(node!=null)
{
int leftCount=node.leftSubTreeCount;
int rightCount=node.rightSubTreeCount;

int currPos=leftCount+parent+1;

if(currPos==k)
return node;
else if(currPos < k)
node=node.left;
else{
node=node.right;
parent=currPos;
}

}

return null;

}``````

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

Tree findkthNode(Tree node, int k)
{
int parent=0;
//

while(node!=null)
{
int leftCount=node.leftSubTreeCount;
int rightCount=node.rightSubTreeCount;

int currPos=leftCount+parent+1;

if(currPos==k)
return node;
else if(currPos < k)
node=node.left;
else{
node=node.right;
parent=currPos;
}

}

return null;

}

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

``````Tree findkthNode(Tree node, int k)
{
int parent=0;
//

while(node!=null)
{
int leftCount=node.leftSubTreeCount;
int rightCount=node.rightSubTreeCount;

int currPos=leftCount+parent+1;

if(currPos==k)
return node;
else if(currPos < k)
node=node.left;
else{
node=node.right;
parent=currPos;
}

}

return null;

}``````

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

Java Implementation.

``````import java.util.*;
/***
*                       5
*             3                  9
*       2          4         6
***/
class TreeNode{
int val;
int size;
TreeNode left;
TreeNode right;
public TreeNode(int val, int size) {
this.val = val;
this.size = size;
}
}
public class KthNodeBinaryTree{
public TreeNode getKthNode(TreeNode root, int kth) {
TreeNode curt = root;
if (curt == null) {
return curt;
}
while (curt != null) {
if (kth > curt.size) {
return null;
}
TreeNode left = curt.left;
if (left == null) {
if (kth == 1) {
return curt;
}
curt = curt.right;
kth--;
} else {
if (kth >= left.size + 1) {
kth = kth - left.size;
if (kth == 1) {
return curt;
} else {
kth = kth - 1;
curt = curt.right;
}
} else {
curt = curt.left;
}
}
}
return curt;
}
public static void main(String[] args) {
KthNodeBinaryTree code = new KthNodeBinaryTree();
TreeNode root = new TreeNode(5, 6);
TreeNode node1 = new TreeNode(3, 3);
TreeNode node2 = new TreeNode(9, 2);
TreeNode node3 = new TreeNode(2, 1);
TreeNode node4 = new TreeNode(4, 1);
TreeNode node5 = new TreeNode(6, 1);
root.left = node1;
root.right = node2;
node1.left = node3;
node1.right = node4;
node2.left = node5;
TreeNode res = code.getKthNode(root, Integer.parseInt(args[0]));
System.out.println((res != null ? res.val : "Your input number is larger than the tree size"));
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````function findNode(N,k) {
if(k <= 1) {
return N;
}
if((N.left != undefined) && N.left.count >= k - 1) {
return findNode(N.left, k - 1);
} else {
return findNode(N.right, k - 1 - N.left.count);
}
}``````

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.