Amazon Interview Question
Country: United States
Interview Type: Phone Interview
In the part where node does have a right child, there is a bug in your code.
If the right child has null as left child your code would return null whereas it should return the right child itself.
In fact, if the node does not have a parent pointer we can solve it in O(n) time. Just add one extra flag to recursion and set it to true when you see the number whose successor is desired. That would be O(n).
void successor(int &flag, node *root, int num)
{
if(root == NULL)
return;
successor(flag, root->left);
if(root->data == num)
flag = 1;
if(flag)
cout << root->data;
successor(flag, root->right, int num);
}
If it does have a parent pointer, in a balanced bst we would be spending O(logn) time. But in the worst case(tree is not balanced), we might spend O(n).
Thanx aj. I fixed the "little" bug. It should be working now :)
However, your code also has one bug. More importantly, the little bug, I do not think it works.
The bug is when you call
successor(flag, root->left);
The function should take 3 parameters, not one.
And about the "real" problem...
Imagine a tree, where root has the value 10. To the left of the node, we have a child with data of 7. And 7 has a right child with data 9. Now, the successor of 9 is the root node, 10. However your code only prints 9 and not the successor
Hi gokayuz.
Thanks for pointing out. Apologies for the sloppiness. I thought you would get the point. Here is the working code.
void successor(int &flag, BST *root, int num)
{
if(root == NULL)
return;
successor(flag, root->left, num);
if(root->key == num)
flag = 1;
else if(flag)
cout << root->key;
successor(flag, root->right, num) ;
}
call this as
int i = 0;
successor(i, root, 9)
The previous code would in fact print all the successors. Just to print one you would have to modify else if part a bit.
void successor(int &flag, BST *root, int num)
{
if(root == NULL)
return;
successor(flag, root->left, num);
if(root->key == num)
flag = 1;
else if(flag){
cout << root->key;
flag = 0;
}
successor(flag, root->right, num) ;
}
"next least", as I understand, is the node that is the smallest that comes after the current node. So, it is asking for the successor.
But you are right, there is some ambiguity about the wording and this needs to be clarified at a interview. But, the given solutions are easy to implement correctly if the question is clarified.
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
using namespace std;
typedef struct tree TREE;
struct tree {
int val;
struct tree *left;
struct tree *right;
};
typedef struct tree TREE;
TREE* makenode(int val) {
TREE* node = (TREE *)malloc(sizeof(struct tree *));
node->val = val;
node->right = NULL;
node->left = NULL;
return node;
}
int findNextLeast(TREE* root, int n){
if(root == NULL)
return -1;
if(root->val == n)
return n;
int l = findNextLeast(root->left, n);
if(l == n)
return root->val;
int r = findNextLeast(root->right, n);
if(r != -1)
return r;
return -1;
}
int main () {
TREE * root = makenode(10);
root->left = makenode(5);
root->right = makenode(15);
root->left->left = makenode(2);
root->left->right = makenode(8);
root->right->left = makenode(12);
root->right->right = makenode(17);
int ret = findNextLeast(root, 8);
if(ret != -1)
printf("\nThe next least : %d", ret);
return 0;
}
Assume we have parent pointer to the node.
public static BSTNode GetNextLeastNode(BSTNode node)
{
if(node == null)
return null;
if(node.Right != null)
{
node = node.Right;
while(node.Left != null)
{
node = node.Left;
}
return node;
}
if( node.Right == null)
{
while(node.Parent != null && node.Parent.Parent != null && node.Parent.Parent.Right == node.Parent)
{
node = node.Parent;
}
if(node.Parent != null && node.Parent.Parent != null )
{
return node.Parent.Parent;
}
else
{
return null;
}
}
}
Can someone just explain what next least node means in simple words before giving any code. Giving an example is important even in interviews. It will also be helpful to people here. Thanks!
I tried to define what the "next least node" is in my solution. in this question, the "next least node" is the node that comes after a specific node in an "in-order traversal of the tree". It is usually called the "successor" of the node.
In layman's terms, if a tree contains nodes with the key values {3, 7, 19 ,23, 26, 31, 40}, the next least node for node{23} is node{26}. For node{3}, the successor is node {7} and naturally node{40} does not have a successor
All answers so far are incorrect. What you are looking for here is the "successor" of the current node. For the given question, I assume all nodes have a pointer two its parent. Otherwise, we need a O(N^2) solution.
There are two cases:
(1) the current node has a right subtree
(2) the right subtree of the current node is NULL.
For (1), the successor is the leftmost child of the right subtree
For (2), we have to go up towards the root till we find a parent node, whose left subtree contains the current node.
Also, note that the node might be the largest element in the tree, and hence there is no successor. In this case, the code returns NULL.
here is the pseudo code:
- gokayhuz February 20, 2014successor(x) { if (x -> right != NULL) // current node DOES have a right node y = x -> right; while (y.left != NULL) // return the minimum element of the right sub-tree y = y -> left; return y; } else { // current node does NOT have a right subtree y = x -> parent; while (y != NULL && x ==y -> right) { // go up the tree x = y; y = y -> parent; } return y; }