## Google Interview Question for SDE1s

Country: United States

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

@majia: I saw you edited the question to include it's not a BST. In this case I assume, you mean, the Binary tree should keep it's complete property after insert. Interesting ;-)

I think one has to do a level order traversal and look for one of these:
- a Node that has either left or right but not both set. If that is met, add the new Node to id. done.
- if no such exists, keep the last node that had no children, that is the last node of the last level of the perfect tree

I think that should do it

``````TreeNode insert(TreeNode root, int val) {
Queue<TreeNode> queue = new LinkedList<>();

TreeNode candidate = null;
queue.add(root);
while(!queue.isEmpty()) {
TreeNode node = queue.pop();

if(node.left != null && node.right == null) (return node.right = new TreeNode(val));
if(node.left == null && node.right != null) (return node.left = new TreeNode(val));
if(node.left == null && node.right == null) candidate = node;
queue.add(node.left);
queue.add(node.right);
}
return (candidate.left = new TreeNode(val));
}``````

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

``````struct TreeNode
{
int value_m;
TreeNode *left, *right;
TreeNode(int value)
: value_m {value}, left {nullptr}, right {nullptr}
{}
};

TreeNode*
insert(TreeNode* node, int val)
{
if(node == nullptr){
return nullptr;
}
const int pivot = node->value;
if(val < pivot){
if(val->left != nullptr){
return insert(val->left,val);
} else {
TreeNode* result = new TreeNode(val);
val->left = result;
return result;
}
} else if(val == pivot){
return node;
} else {
assert(val > pivot);
if(val->right != nullptr){
return insert(val->right,val);
} else {
TreeNode* result = new TreeNode(val);
val->right = result;
return result;
}
}
}``````

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

...if it's not a BST you can put it everywhere, just grab a node and insert it.

Therefore I assume the question aimed at inserting a node into a complete binary search tree (which is ordered). Complete means all levels except the last are full, how ever, it didn't say, the result must be a complete BST again.

So I assume, you need to find the node to insert and insert it. Finding the node to insert can be done using binary search which is only guaranteed to be efficient if the tree is balanced, a complete tree is balanced.

``````// assumed BST property left <= current <= right
TreeNode insert(TreeNode root, int val) {
if(val <= root.value) {
if(root.left == null) return (root.left = new TreeNode(val));
return insert(root.left, val);
}
if(root.right == null) return (root.right = new TreeNode(val));
return insert(root.right, val);
}``````

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

``````// Function to insert a new node in complete binary tree
void insertIntoCompleteBinaryTree(node **root, int data)
{
Queue* queue = createQueue(SIZE);

// Create a new node for given data
node *temp = newNode(data);

// If the tree is empty, initialize the root with new node.
if (!*root)
*root = temp;

else
{
// get the front node of the queue.
node* front = getFront(queue);

// If the left child of this front node doesn’t exist, set the
// left child as the new node
if (!front->left)
front->left = temp;

// If the right child of this front node doesn’t exist, set the
// right child as the new node
else if (!front->right)
front->right = temp;

// If the front node has both the left child and right child,
// Dequeue() it.
if (hasBothChild(front))
Dequeue(queue);
}

// Enqueue() the new node for later insertions
Enqueue(temp, queue);``````

}

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

I think the key is that the tree is complete. If the tree is complete it may be stored in array. Adding a new element (leaf) to the complete tree is done by writing the element to the last position of the array. If the array is full it needs to be resized. Resizing may be done without copying all previous elements to the new array by allocating memory blocks of same size, linking them, and filling with the data.

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

Complete tree may be stored in array. adding an element is just writing to the last position of the array

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

Complete tree may be stored in array. Adding an element to the tree is then done by writing to position array.size(). Resizing may be needed if there is no room. It may be done without copying all previous alements

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

Given tree is a complete Binary Tree. We can take advantage of complete binary tree properties.
Keep a count of element in the tree. Based on the count of elements we can find path. Lets say path for root element is "0".
Path for second element will be "0 L"
For Third "0 R"
For Fourth "0 L L"
For Fifth "0 L R"

Logic:
Lets say we need to find path for 7th element.
Find level of seventh element. Its 3
Now find number of elment on its previous level - Its 4
Now Path of 7th element - path of '((7 - 4)th element + "R"'

So if we need to find path for nth element and its level is 'l'.
Formula for path will be :- path of ( n - pow(2, l -1))th element + (n % 2 == 0 ? 'L' : 'R')

Note: u need to small modification in algo to handle corner cases

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

``````Given tree is a complete Binary Tree. We can take advantage of complete binary tree properties.
Keep a count of element in the tree. Based on the count of elements we can find path. Lets say path for root element is "0".
Path for second element will be "0 L"
For Third "0 R"
For Fourth "0 L L"
For Fifth "0 L R"

Logic:
Lets say we need to find path for 7th element.
Find level of seventh element. Its 3
Now find number of elment on its previous level - Its 4
Now Path of 7th element - path of '((7 - 4)th element + "R"'

So if we need to find path for nth element and its level is 'l'.
Formula for path will be :- path of ( n - pow(2, l -1))th element + (n % 2 == 0 ? 'L' : 'R')

Note: u need to small modification in algo to handle corner cases``````

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

``````package google;

import concepts.TreeNode;

public class InsertIntoCompleteBinaryTree {

public enum Result {
foundPos, inserted, notFound
};

public static void main(String args[]) {
TreeNode<Integer> root = new TreeNode<Integer>(1);
root.left = new TreeNode<Integer>(2);
root.right = new TreeNode<Integer>(3);
root.left.left = new TreeNode<Integer>(4);
root.left.right = new TreeNode<Integer>(5);

int maxHeight = findHeight(root, 0);

insert(6, 0, maxHeight, root);
System.out.println(root.right.left);
}

private static Result insert(int elem, int height, int maxHeight, TreeNode<Integer> cur) {
if (cur == null) {
if (height < maxHeight) {
return Result.foundPos;
} else {
return Result.notFound;
}
}
Result res;
if ((res = insert(elem, height + 1, maxHeight, cur.left)) == Result.foundPos) {
cur.left = new TreeNode<Integer>(6);
return Result.inserted;
} else if (res == Result.inserted) {
return res;
} else if ((res = insert(elem, height + 1, maxHeight, cur.right)) == Result.foundPos) {
cur.right = new TreeNode<Integer>(6);
return Result.inserted;
} else {
return res;
}
}

private static int findHeight(TreeNode<Integer> cur, int height) {
if (cur == null) {
return height;
} else {
return findHeight(cur.left, height + 1);
}
}
}``````

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

What if we don't know the elements count.
In this case we solve it efficient as follow l.
1- Follow the most left path and count levels number L.
2- Follow the most right path of root's left node and count the levels number L2.
3- If L1 == L2, then new will be inserted in root right tree, otherwise it will be inserted in root's left tree.
4- Repeat the above the steps to either root left or right tree ( according to test in previous step).
this alogorithm runs in log (n)^2 is faster than n.

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

With constraint of supporting a limited no. of nodes. Time of insertion can be finished in O(logn) time:

int pathVector = 0; //Maximum elements supported is Integer.MAX_VALUE+1 .May use array to extend the limit.
public void insert(BinaryTreeNode root, int value){
if(pathVector < 0){
//overflow happened
throw new RuntimeException("Too many elements");
}
pathVector ++;
if(root == null){
root = new BinaryTreeNode(value);
}

BinaryTreeNode parent = root;
int i = findLeftmostOne(pathVector);
while(i > 1){
if(checkZero(p, --i)){
parent = parent.getLeft();
} else {
parent = parent.getRight();
}
}
if(checkZero(pathVector, --i)){
parent.setLeft(new BinaryTreeNode(value));
} else {
parent.setRight(new BinaryTreeNode(value));
}
count++;

pathVector = next(pathVector, log(count, 2));
}

public boolean checkZero(int v, int i){
int p = v & (1 << i);
return p == 0;
}

public int findLeftmostOne(int v){
int mask = 0x8000;
int leftmostOneIndex = 30;
int j = v & mask;
while(j == 0){
leftmostOneIndex--;
mask = mask >> 1;
j = v & mask;
}
return leftmostOneIndex;
}

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

``Complete binary tree is the property of heap data structure, in which data can be accomodated in an array/arraylist(for insertion).There the new node can be added to last internal node which will be Math.floor(arraylist.size()/2)``

. Insertion into he arraylist is amortized constant time as ArrayList implements RandomAccess Interface.

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

Given that it is a complete binary tree and assuming you have created the tree by insertion, all you really need to know is also maintain the count of elements in the tree.

If the tree has n nodes in it and you want to add the (n+1)th node, then just look at the bits in number (n+1) from least significant to most significant (ignore the very last 1 (most significant digit)). Start from the root and if a bit is 0, it means go left, if it is 1 it means go right. Special case insertion in empty tree to just add root.
For example if the tree has 1 node in it already, then n+1 == 2, which is 10 in binary. Meaning first go left from the root and then ignore the most significant 1, meaning insert it left of root.
If it has 2 nodes in it already, then n+1 == 3, which is 11 in binary.
Meaning first go right from the root and then ignore the most significant 1, meaning insert it right of root.
If it has 3 nodes in it already, then n+1 == 4 which is 100 in binary.
Meaning first go left(0) from the root, then go left(0) once more and then ignore the most significant 1, meaning insert it as left of left of root.
...

This insertion algorithm is O(log(n))

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

I assume that after inserts the tree should stay complete.
First we find the parent for the new node using a recursive in-order traversal, looking for a node which has a child missing, and which has minimum depth. One optimization applied is that when the minimum depth gets better we can stop searching.
Time: O(N).
Space: O(log N).

``````class Node {
public:
Node(int val)
{
val_ = val;
left_ = right_ = NULL;
}
int val_;
Node *left_, *right_;
};

void FindParent(Node *n, Node* &parent, int &parent_min_depth, bool &stop_searching, int depth = 0)
{
if (n &&
!stop_searching)
{
FindParent(n->left_, parent, parent_min_depth, stop_searching, depth + 1);

if (!n->left_ ||
!n->right_)
{
if (depth < parent_min_depth) {
if (parent_min_depth != numeric_limits<int>::max()) {
stop_searching = true;
}
parent_min_depth = depth;
parent = n;
}
}

FindParent(n->right_, parent, parent_min_depth, stop_searching, depth + 1);
}
}

void Insert(Node *root, int val)
{
Node *parent;
int parent_min_depth = numeric_limits<int>::max();
bool stop_searching = false;
FindParent(root, parent, parent_min_depth, stop_searching);

Node *n = new Node(val);
if (!parent->left_) {
parent->left_ = n;
} else {
parent->right_ = n;
}
}``````

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

it's similar to adding an element to a prioritye queue. Store all the nodes in an array list. when you need to insert a node, insert it at the end of the array list. parent of a node at index i will be floor(i/2)

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

O(N) time complexity

``````public static void insertNodeToTree(TreeNode root,int val){
TreeNode node = new TreeNode(val);
if(root==null){
return;
}else if(root.left==null){
root.left=node;
return;
}else if(root.right==null){
root.right=node;
return;
}

int left_rHeight = rightMostHeight(root.left);
int right_rHeight =  rightMostHeight(root.right);

if(left_rHeight==right_rHeight){
insertNodeToTree(root.left,val);
}else{
insertNodeToTree(root.right,val);
}
}

public static int rightMostHeight(TreeNode root){
if(root==null){
return 0;
}
return 1+rightMostHeight(root.right);
}``````

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

O(log(N)) Time complexity solution:

``````public static void insertNodeToTree(TreeNode root,int val){
TreeNode node = new TreeNode(val);
if(root==null){
return;
}else if(root.left==null){
root.left=node;
return;
}else if(root.right==null){
root.right=node;
return;
}

int left_rHeight = rightMostHeight(root.left);
int right_rHeight =  rightMostHeight(root.right);

if(left_rHeight==right_rHeight){
insertNodeToTree(root.left,val);
}else{
insertNodeToTree(root.right,val);
}
}

public static int rightMostHeight(TreeNode root){
if(root==null){
return 0;
}
return 1+rightMostHeight(root.right);
}``````

Add a Comment
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.

Learn More

### 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.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More