Google Interview Question
SDE1sCountry: United States
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);
}
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;
}
}
}
...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);
}
// 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);
}
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.
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
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
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);
}
}
}
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.
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;
}
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.
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))
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;
}
}
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);
}
@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
- Chris May 11, 2017