Google Interview Question
Software Engineer / DevelopersCountry: United States
I don't understand what does n mean? Can you explain more about the question and answer?
//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;
}
}
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
}
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;
}
}
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.
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
*/
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;
}
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;
}
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);
}
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;
}
}
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;
}
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;
}
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;
}
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"));
}
}
for inorder traversal:
- Adi November 07, 2014=> if k-left == 1: n is curr node
=> else if k > left+1 : n = n.right, k = k-left-1
=> else : n = n.left