## Google Interview Question for Backend Developers

Country: United States

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

``````public class Solution {

static class TreeNode{
int val;
int numberOfChildren;
TreeNode left;
TreeNode right;

public TreeNode(int val){
this.val = val;
}
}

public static int findKthOfInorder(TreeNode root, int k) {
if (root == null) return -1;

int leftChildCount = (root.left != null) ? root.left.numberOfChildren + 1 : 0;

if (k == leftChildCount + 1) return root.val;
else if (k <= leftChildCount) return findKthOfInorder(root.left, k);
else return findKthOfInorder(root.right, k - leftChildCount - 1);
}

public static TreeNode insertInorderAtKth(TreeNode root, int k, int newVal) {
if (root == null) return k == 1 ? new TreeNode(newVal) : null;

int leftChildCount = (root.left != null) ? root.left.numberOfChildren + 1 : 0;

if (k == leftChildCount + 1) {
TreeNode newNode = new TreeNode(newVal);
newNode.left = root.left;
newNode.right = root;
newNode.numberOfChildren = root.numberOfChildren + 1;

root.left = null;
root.numberOfChildren -= leftChildCount;
return newNode;
} else if (k <= leftChildCount) {
root.left = insertInorderAtKth(root.left, k, newVal);
root.numberOfChildren += root.left != null ? 1: 0;
} else {
root.right = insertInorderAtKth(root.right, k - leftChildCount - 1, newVal);
root.numberOfChildren += root.right != null ? 1: 0;
}

return root;
}
}``````

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

this is a bit dumb. binary tree always has two children, so not sure what is the point of this question.

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

Test

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

Test

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.