Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Written Test
void GetInOrderSucc(BNode *Root)
{
BNode *Curr = Root;
BNode *RNext;
while(Curr)
{
RNext = Curr->Right;
if(!RNext)
{
Curr = Curr->Left;
continue;
}
while(!(RNext->Left) && RNext->Left != Curr)
RNext = RNext->Left;
if(!(RNext->Left))
{
RNext->Left = Curr;
Curr = Curr->Right;
}
else
{
RNext->Left = NULL;
Curr->Next = RNext;
Curr = Curr->Left;
}
}//while
}
typedef Node* NodePtr;
void FindSuccessor(NodePtr root, int k, NodePtr& successor)
{
if (root == NULL)
{
return;
}
if (root->data <= k)
{
FindSuccessor(root->right, k, successor);
}
if (successor == NULL || root->data < successor->data )
{
successor = root;
}
FindSuccessor(root->left, k, successor);
}
Reposting with formatted code.
/* Assuming no pointer to parent node.
* If we had a pointer to the parent node,
* the code to find successor is much less
* messier. Refer Cormen.
*/
typedef struct node {
int data;
struct node *left;
struct node *right;
struct node *next;
} Node;
/* Find if the node with the given data
* is present in the given BST. Takes
* pointer to root as the initial argument.
*/
Node* FindNode (int data, Node *node) {
if (node == NULL) return NULL;
if (data == node->data) return node;
if (data < node->data)
return FindNode (node->left, data);
else
return FindNode (node->right, data);
}
/* The routine that finds the successor of
* a given node in the BST. Utilizes FindNode()
*/
Node* FindSuccessor (int data, Node *root) {
Node *node = FindNode (data, root);
if (node == NULL) return NULL; /* Node not present */
Node *temp, *succ;
/* The case where the given node has a right child.
* So the successor is the left most node in the right
* sub tree.
*/
if ( (succ = node->right) != NULL) {
while (succ->left != NULL) succ = succ->left;
return succ; /* This is the successor */
}
/* The case where the given node has no right child.
* The successor is the lowest ancestor whose left child
* is the given node or whose left child also is an ancestor
* of the given node.
temp = root, parent = NULL;
while (temp != NULL && temp != node) {
/* Data is in the left sub tree. So we
* surely have a successor. temp might
* be a possible successor. Save it and descend
* further down the tree.
if (data < temp->data) {
succ = temp;
temp = temp->left;
}
else {
/* Data is in the right subtree. Hence, temp
* temp is surely not the successor. So descend
* without saving temp.
*/
temp = temp->right;
}
}
return succ; /* If no successor, then anyhow succ
* is initialized to NULL, which is returned.
*/
}
/* This is the routine that finally fills in
* the next pointers of each node in the BST.
* Travserse each node in the tree and call
* FindSuccessor() for each. Start with node = root.
*/
void getInorderSuccessor (Node *node, Node *root) {
if (node == NULL) return;
node->next = FindSuccessor (node->data, root);
/* Proceed recursively in any fashion. Inorder, pre or post.
* I'm traversing in pre-order. Doesn't matter which order
*/
getInorderSuccessor (node->left, root);
getInorderSuccessor (node->right, root);
}
here you go
Node GetInorderSuccessor(Node node,Node nextNode){
if(node->right)
node->next=GetInorderSuccessor(node->right,nextNode);
else
node->next=nextNode;
if(node->left)
return GetInorderSuccessor(node->left,node);
else
return node;
}
call as GetInorderSuccessor(Root,null) and ignore the returned node
I think the following is much simpler and efficeint implementation
*/
void getInorderSuccessor (Node node) {
if (node.left == NULL && node.right == null) {
node.next = stack.pop(); //stack is a global variable
return;
}
stack.push(node);
getInorderSuccessor (node.left);
getInorderSuccessor (node.right);
node.next = node.right;
}
node->next = FindSuccessor (node->data, root);
/* Proceed recursively in any fashion. Inorder, pre or post.
* I'm traversing in pre-order. Doesn't matter which order
*/
getInorderSuccessor (node->left, root);
getInorderSuccessor (node->right, root);
}
/*
public class TreeNode {
public TreeNode levelnext,next,left, right;
public int data;
TreeNode(int data) {
this.data = data;
}
}
*/
static TreeNode next;
public static void inorderSuccersor(TreeNode root) {
if (root != null) {
inorderSuccersor(root.right);
root.next = next;
next = root;
inorderSuccersor(root.left);
}
}
Just modify the normal inorder function.
void inorder(Node* r,Node* & tmp)
{
if (r==0)
return;
inorder(r->left,tmp);
tmp->next=r;
tmp=r;
inorder(r->right,tmp);
}
Push elements in stack in inorder.
Then pop each element and assign its successor. Complexity O(n);
Stack stack
Inorder (node *root)
{
if (root == NULL)
return;
Inorder (root->left);
stack.push (root);
Inorder (root->right);
}
node *p1=NULL, *p2=NULL;
while (!stack.empty) {
p2 = stack.pop;
p2->next = p1;
p1 = p2;
}
To find next Inorder successor is same as find next bigger node than given node.So next bigger node is lies on either right child of given node (if right child is present) or the nearest ancestor who's left side node is situated.
struct node
{
int data;
struct node *left;
struct node * right;
};
typedef struct node * Tree;
Tree * getNextInorderNode(Tree root)
{
Tree succ = NULL;
while(root)
{
succ = root;
root = root -> left;
}
return succ;
}
Tree * getInorderSucc(Tree root, const Tree n)
{
Tree succ = NULL;
if(n == NULL)
return NULL;
if(n->right)
return getNextInorderNode(n->right);
while(root)
{
if(root->data > n->data)
{
succ = root;
root = root -> left;
}
else if (root->data < n->data)
root = root ->right;
else
break;
}
return succ;
}
//Traverse the tree using Inorder traversal and find the Successor of each node and set it
// Call Inorder traversal by invoking inorderTraversal(rootNode);
public void inorderTraversal(TreeNode n) {
if (n == null)
return;
inorderTraversal(n.getLeft());
// Process The Node and get the Successor of the Node x
TreeNode succesor = findSuccessor(n);
n.setSuccessor(succesor);
if (succesor != null)
System.out.println("Successor of Node n::" + n.getValue() + " is "
+ n.getSuccessor().getValue());
else
System.out.println("Successor of Node n::" + n.getValue()
+ " is null");
inorderTraversal(n.getRight());
}
public TreeNode findSuccessor(TreeNode x) {
if (x.getRight() != null) {
return findMinumum(x.getRight());
}
TreeNode y = x.getParent();
while (y != null && x == y.getRight()) {
x = y;
y = y.getParent();
}
return y;
}
public TreeNode findMinumum(TreeNode x) {
while (x.getLeft() != null) {
x = x.getLeft();
}
return x;
}
public void inorderTraversal(TreeNode n) {
if (n == null)
return;
inorderTraversal(n.getLeft());
// Process The Node and get the Successor of the Node x
TreeNode succesor = findSuccessor(n);
n.setSuccessor(succesor);
inorderTraversal(n.getRight());
}
public TreeNode findSuccessor(TreeNode x) {
if (x.getRight() != null) {
return findMinumum(x.getRight());
}
TreeNode y = x.getParent();
while (y != null && x == y.getRight()) {
x = y;
y = y.getParent();
}
return y;
}
public TreeNode findMinumum(TreeNode x) {
while (x.getLeft() != null) {
x = x.getLeft();
}
return x;
}
Node * get_inorder_successor(Node * node, Node * successor = NULL) {
if(node -> right != NULL)
successor = get_inorder_successor(node->right,successor);
node->successor_node = successor;
successor = node;
if(node -> left != NULL)
successor = get_inorder_successor(node->left, successor);
return successor;
}
I think the following is much simpler and efficeint implementation
*/
void getInorderSuccessor (Node node) {
if (node.left == NULL && node.right == null) {
node.next = stack.pop(); //stack is a global variable
return;
}
stack.push(node);
getInorderSuccessor (node.left);
getInorderSuccessor (node.right);
node.next = node.right;
}
- m May 15, 2012private static Node next = null; public static void FillInOrderSuccessors(Node root) { if (root == null) return; FillInOrderSuccessors(root.right); root.next = next; next = root; FillInOrderSuccessors(root.left); }