Google Interview Question Software Engineer / Developers
Country: United States
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;
}
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.
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.
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.
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;
}
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
}
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)?
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
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);
}
}
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;
}
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;
}
#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;
insertByrecursion(4,&head);
insertByrecursion(3,&head);
insertByrecursion(5,&head);
insertByrecursion(8,&head);
insertByrecursion(14,&head);
insertByrecursion(87,&head);
insertByrecursion(1,&head);
printf(" elements in BST\n");
inorder(head);
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;
}
#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;
insertByrecursion(4,&head);
insertByrecursion(3,&head);
insertByrecursion(5,&head);
insertByrecursion(8,&head);
insertByrecursion(14,&head);
insertByrecursion(87,&head);
insertByrecursion(1,&head);
printf(" elements in BST\n");
inorder(head);
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;
}
{
#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;
insertByrecursion(4,&head);
insertByrecursion(3,&head);
insertByrecursion(5,&head);
insertByrecursion(8,&head);
insertByrecursion(14,&head);
insertByrecursion(87,&head);
insertByrecursion(1,&head);
printf(" elements in BST\n");
inorder(head);
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;
}
}
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);
}
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.
}
}
The key in this problem is to clarify whether there are parent pointers?
- xuyan.nus May 07, 2014Because 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)