## Google Interview Question for Software Engineer / Developers

Country: United States

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

The key in this problem is to clarify whether there are parent pointers?
Because parent pointers are not necessary for BST.

Case 1: Has parent pointers.
The algorithm proposed by Zol is a great answer.
1.1: The leftmost child of the right child, if your current node has a right child.
1.2: If not, find a parent whose left child is the node you're currently at.
1.3: If not, there is no successor.

Case 2: No parent pointers.
1.0: keep a global variable, say "find_the_node", and initialized as "false";
1.1: DO "in-order traversal method".
1.2: If find, set "find_the_node" to be true.
1.3: The next traversal node is the successor. Otherwise, no successor.

Complexity:
Case 1: Big-O worst case: O(lg(n))
Case 2: Big-O worst case: O(n)

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

This problem is similar to finding the next inorder successor of the given node.

``````public static void  findNextLargest(TreeNode node,TreeNode target){
TreeNode temp=null;
if(target.right!=null){
temp = target.right;
while(temp.left!=null){
temp = temp.left;
}
System.out.println(temp.val);
return;
}

while(node!=null){
if(target.val < node.val){
temp = node;
node = node.left;
}else if(target.val > node.val){
node = node.right;
}else
break;
}
if(temp!=null)
System.out.println(temp.val);
return;

}``````

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

I don't see why you need 2 node parameters to find the in order successor of a given node...
Besides, you don't even need to compare the values of the nodes in order to find the successor.

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

The question is ambiguous (check my post of clarifying questions).

There are many, many factors involved. Both of you "assumed" the factors based on whatever version of "inorder successor" you each had experience with.

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

We need the root here as a node does not have a parent pointer. So, the treenode structure has only two pointers : Left child and right child.

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

@ coder : Exactly. Having root node would help to solve the corner case in which the given node is the right leaf node on a left subtree:

In the above case, R would be the node that has to be returned :)

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

The question is basically find the in order successor of the given node.

If the node has a right child, then the successor will be the leftmost element of the right child.
If it does not, then we go up through the parents until we "do a right turn". That is, we stop when the current node is the left child of the parent. That's when we have encountered the in order successor.

Here is the code:

``````public Node succ(Node n) {
if(n == null)
return null;
if(n.right != null)
return minNode(n.right);
else {
Node tmp = n;
while(tmp.parent != null && tmp.parent.left != tmp)
tmp = tmp.parent;
return tmp.parent;
}
}

private Node minNode(Node n) {
if(n == null)
return null;
while(n.left != null)
n = n.left;
return n;
}``````

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

You are assuming that child nodes keep references to their parents.

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

Even though this question has been beaten to death, here is my two cents on it :
We need to find in-order successor to the a node in BST
In addition to std BST, we'll need a pointer to the parent

Algorithm:

``````If (node has a rightChild){
find min in right subtree i.e. go right and keep going left
till you encounter a NULL
}
else if (node is a leftChild of its parent){
parent is the in order successor
}
else{
node is the right Child.
while(parent != NULL){
1. Keep going up the parents till you find a node that is
the left child of its parent. That parent is the in order successor
or 2. Keep going up till you find a node >= current node
}
if no successor found this means that the node was the rightmost
one and has no successor
}``````

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

It depends.
1) Are you given a key or a node(address/reference)?
2) Are there parent pointers?
3) Do you mind O(n) or do you insist on O(lg n)?

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

parent given. amortized O(1).

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

In that case:
- Augment each node with "succ" pointer.
- Augment insert/delete/rebalance operations to keep "succ" pointer valid
-> E.g. if you insert a node, walk down it's right subtree, or if it doesn't have one, use parent pointers to find succ., then fill the "succ" pointer

-> Now create a succ(reference/pointer to node) function that returns the succ. in O(1) time... O(1) time is still O(1) amortized

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

``````class Node{
int data;
Node left;
Node right;
}
public class BST_FindNextLrgstMin {
public static void main(String arg[])
{
BST_FindNextLrgstMin bstfm=new BST_FindNextLrgstMin ();
Node root=bstfm.CreateBST();

//givenn values in bst are 4,5,6,7,8,9,10
//then first largest is 10,
//second largest is 9 and so on
Node nxtlrgst=bstfm.FindNextLargest(root, 15, root);
System.out.println("\nNext Largest of 15:"+nxtlrgst.data);
}

Node FindNextLargest(Node root, int val,Node current){
//first find node with given value
Node nxtlrgst=null;
if (root==null){
nxtlrgst=current;
}

if (root.data<val){
current = root;
nxtlrgst=FindNextLargest(root.right,val,current);
}else if (root.data>val){
nxtlrgst=FindNextLargest(root.left,val,current);
}else if(root.data==val){
if(root.right==null)
{
nxtlrgst=current;
}else{
BST_FindNextLrgstMin temp=new BST_FindNextLrgstMin ();
nxtlrgst=temp.FindMax(root.left);
}
}
return nxtlrgst;
}

Node FindMax(Node root)
{
//In BST rightmost Node will max ,
//hence just traverse right path from root to get Max number
Node max;
try{
if (root.right!=null){
max=FindMax(root.right);
}else{
System.out.println("\nFrom If Block...");
return root;
}
}catch(NullPointerException e){
System.out.println("\nFrom Catch Block...");
return root;
}
return max;
}
Node CreateBST()
{
Node root=new Node();
root.data=11;
Node n1=new Node();		n1.data=7;		root.left=n1;
Node n2=new Node(); 	n2.data=15;		root.right=n2;

Node n3=new Node();		n3.data=5;		n1.left=n3;
Node n4=new Node();		n4.data=9;		n1.right=n4;
Node n5=new Node();		n5.data=13;		n2.left=n5;
Node n6=new Node();		n6.data=17;		n2.right=n6;

Node n7=new Node();		n7.data=4;		n3.left=n7;
Node n8=new Node();		n8.data=6;  	n3.right=n8;
Node n9=new Node();	    n9.data=8;  	n4.left=n9;
Node n10=new Node();	n10.data=10; 	n4.right=n10;
Node n11=new Node();	n11.data=12; 	n5.left=n11;
Node n12=new Node();	n12.data=14; 	n5.right=n12;
Node n13=new Node();	n13.data=16; 	n6.left=n13;
Node n14=new Node();	n14.data=18; 	n6.right=n14;

return (root);
}
}``````

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

For anyone interested I'm putting a small visual presentation at my blog:
ptechpedia (dot) blogspot (dot) com

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

``````if(ptr->right==NULL)
cout<<"No next largest elemnt";
else
{
node *p=ptr->right;
while(p->left!=NULL)
p=p->left;
}
return p->key;``````

Inorder successor is the leftmost child of the rightchild of the given node.

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

``````bool found = false;
Node* findNext(Node* root, Node* node)
{

if (root->left)
{
Node* n = findNext(root->left, node);
if (n != NULL) return n;
}

if (found)
{
std::cout << "found: " << root->data << "\n";
return root;
}
else if (root == node)
{
found = true;
}

if (root->right)
{
Node* n = findNext(root->right, node);
if (n != NULL) return n;
}

return NULL;
}``````

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

Here is a O(log n) time solution.

``````void printSuccessor(TreeNode* root, int target){
if(!root) return;
TreeNode* cur = root;
int successor = target-1;
//find node with value = target
while(cur){
if(cur->val=target)
break;
//as you go down, store the value which is >target
if(cur->val<target)
cur=cur->right;
else{
successor = cur->val;
cur=cur->left;
}
}
if(cur && cur->right){ //find node with value = target and this node has right child
cur = cur->right;
if(cur->left)
cur=cur->left;
successor = cur->val;
}
if(successor>=target)
cout << successor << endl;
}``````

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

``````#include <stdio.h>

/*
For a given node in binary search tree find a next largest number in search tree.
*/
#include <stdio.h>
#include<stdlib.h>

struct node {

int data;
struct node *left;
struct node *right;

};
struct node *head = NULL;

void insertByrecursion(int data,struct node **root){

if(*root == NULL) {

struct node *temp = (struct node *)malloc(sizeof(struct node));
memset(temp,0,sizeof(struct node));
temp->data = data;
*root = temp;

printf("\tinsert 0x%x  %d \n",temp,temp->data);

return;
}

if((*root)->data > data)
insertByrecursion(data,&(*root)->left);
else
insertByrecursion(data,&(*root)->right);

}

void inorder(struct node *ptr){

if(ptr == NULL)
return ;

inorder(ptr->left);
printf("\t%d ",ptr->data);

inorder(ptr->right);

}
void inorderfind(struct node *ptr){

if(ptr == NULL)
return ;

inorder(ptr->left);
if(printed == 0) {
printf("\t%d ",ptr->data);
printed = 1;
}

inorder(ptr->right);

}

struct node  *find(int n,struct node *ptr){

if(ptr == NULL){
printf("    NULL \n" );
return;
}

if(ptr->data == n){
printf(" %d   found \n",n);
return ptr;

}else {

printf("   traverse \n");
if(ptr->data > n)
return find(n,ptr->left);
else
return find(n,ptr->right);
}

printf("     Junk");

}

struct node * find_min(struct node *ptr) {

if(ptr->left == NULL)
return ptr;

while(ptr->left){
ptr = ptr->left;
}

return ptr;

}

int main(){

int search = 14;
struct node *temp1,*prev,*temp2;

printf(" elements in BST\n");

printf("\n  Next item is ");
prev = temp1 = head;
while(temp1){

if(temp1->data == search){
break;
}
prev = temp1;
if (temp1->data > search)
temp1 = temp1->left;
else
temp1 = temp1->right;
}

if((temp1) && (temp1 != prev)){

if(temp1->right == NULL)
printf(" next item is %d \n",prev->data);
else {
temp2 = find_min(temp1->right);
printf(" %d  \n",temp2->data);
}

}else {

if(temp1->right == NULL)
printf("  no next item\n");
else {
temp2 = find_min(temp1->right);
printf(" %d  \n",temp2->data);
}

}

return 0;

}``````

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

``````#include <stdio.h>

/*
For a given node in binary search tree find a next largest number in search tree.
*/
#include <stdio.h>
#include<stdlib.h>

struct node {

int data;
struct node *left;
struct node *right;

};
struct node *head = NULL;

void insertByrecursion(int data,struct node **root){

if(*root == NULL) {

struct node *temp = (struct node *)malloc(sizeof(struct node));
memset(temp,0,sizeof(struct node));
temp->data = data;
*root = temp;

printf("\tinsert 0x%x  %d \n",temp,temp->data);

return;
}

if((*root)->data > data)
insertByrecursion(data,&(*root)->left);
else
insertByrecursion(data,&(*root)->right);

}

void inorder(struct node *ptr){

if(ptr == NULL)
return ;

inorder(ptr->left);
printf("\t%d ",ptr->data);

inorder(ptr->right);

}
void inorderfind(struct node *ptr){

if(ptr == NULL)
return ;

inorder(ptr->left);
if(printed == 0) {
printf("\t%d ",ptr->data);
printed = 1;
}

inorder(ptr->right);

}

struct node  *find(int n,struct node *ptr){

if(ptr == NULL){
printf("    NULL \n" );
return;
}

if(ptr->data == n){
printf(" %d   found \n",n);
return ptr;

}else {

printf("   traverse \n");
if(ptr->data > n)
return find(n,ptr->left);
else
return find(n,ptr->right);
}

printf("     Junk");

}

struct node * find_min(struct node *ptr) {

if(ptr->left == NULL)
return ptr;

while(ptr->left){
ptr = ptr->left;
}

return ptr;

}

int main(){

int search = 14;
struct node *temp1,*prev,*temp2;

printf(" elements in BST\n");

printf("\n  Next item is ");
prev = temp1 = head;
while(temp1){

if(temp1->data == search){
break;
}
prev = temp1;
if (temp1->data > search)
temp1 = temp1->left;
else
temp1 = temp1->right;
}

if((temp1) && (temp1 != prev)){

if(temp1->right == NULL)
printf(" next item is %d \n",prev->data);
else {
temp2 = find_min(temp1->right);
printf(" %d  \n",temp2->data);
}

}else {

if(temp1->right == NULL)
printf("  no next item\n");
else {
temp2 = find_min(temp1->right);
printf(" %d  \n",temp2->data);
}

}

return 0;

}``````

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

{
#include <stdio.h>

/*
For a given node in binary search tree find a next largest number in search tree.
*/
#include <stdio.h>
#include<stdlib.h>

struct node {

int data;
struct node *left;
struct node *right;

};
struct node *head = NULL;

void insertByrecursion(int data,struct node **root){

if(*root == NULL) {

struct node *temp = (struct node *)malloc(sizeof(struct node));
memset(temp,0,sizeof(struct node));
temp->data = data;
*root = temp;

printf("\tinsert 0x%x %d \n",temp,temp->data);

return;
}

if((*root)->data > data)
insertByrecursion(data,&(*root)->left);
else
insertByrecursion(data,&(*root)->right);

}

void inorder(struct node *ptr){

if(ptr == NULL)
return ;

inorder(ptr->left);
printf("\t%d ",ptr->data);

inorder(ptr->right);

}
void inorderfind(struct node *ptr){

if(ptr == NULL)
return ;

inorder(ptr->left);
if(printed == 0) {
printf("\t%d ",ptr->data);
printed = 1;
}

inorder(ptr->right);

}

struct node *find(int n,struct node *ptr){

if(ptr == NULL){
printf(" NULL \n" );
return;
}

if(ptr->data == n){
printf(" %d found \n",n);
return ptr;

}else {

printf(" traverse \n");
if(ptr->data > n)
return find(n,ptr->left);
else
return find(n,ptr->right);
}

printf(" Junk");

}

struct node * find_min(struct node *ptr) {

if(ptr->left == NULL)
return ptr;

while(ptr->left){
ptr = ptr->left;
}

return ptr;

}

int main(){

int search = 14;
struct node *temp1,*prev,*temp2;

printf(" elements in BST\n");

printf("\n Next item is ");
prev = temp1 = head;
while(temp1){

if(temp1->data == search){
break;
}
prev = temp1;
if (temp1->data > search)
temp1 = temp1->left;
else
temp1 = temp1->right;
}

if((temp1) && (temp1 != prev)){

if(temp1->right == NULL)
printf(" next item is %d \n",prev->data);
else {
temp2 = find_min(temp1->right);
printf(" %d \n",temp2->data);
}

}else {

if(temp1->right == NULL)
printf(" no next item\n");
else {
temp2 = find_min(temp1->right);
printf(" %d \n",temp2->data);
}

}

return 0;

}
}

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

I found this very easy

``````public int findMax(Node n) {
if (n == null)
return 0;//throw exception here possibly
if (n.right == null) {
return n.value;
}
return findMax(n.right);
}``````

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

what???
Can you pls explain???
Not making sense!

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

nextLargestNode(node) = {
max( node.parent, node-right)
}

the problem is we may don't know the parent from given node, so we can use something like
Search(Node) {
Node = parent;
// Do ordinary search in BST for each visited node
if(node is parent_left or node is parent_right) {
return nextLargest(parent, node) // now we have parent information.
}
}

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.