Jun 112012

Given a pointer to the node in a binary tree, write code to find its inorder successor. You may assume each node to also have a pointer to the parent node (along with pointer to right and left sub-trees). Hence, the structure of Node will be

struct Node { int data; Node* lptr; // pointer to the left subtree Node* rptr; // pointer to the right subtree Node* parent; // Pointer to the parent Node (null for root of tree) };

**For example:** if we have the below binary tree, then

Node Inorder Successor ------- ---------------------- 15 17 18 19 50 NULL 20 30 7 15

**Solution:**

If the Node has right child, then the in-order successor of the node ca be found by

- Move to the right child
- keep moving to the left child untill the left child becomes NULL. When we get a node for which the left child is null, return that node.

For example: 1. To find the in-order successor of 18 - Move to the right child, i.e 19 - Since the left child of 19 is NULL, return 19 2. To find the in-order successor of 15 - Move to the Right child, i.e 20 - Move to the left child, i.e 18 and keep moving to left child till we get a NULL pointer as left child, i.e 17. Return 17.

If the Right child is NULL, then in-order successor can be found using the parent Node,

- Move to the parent Node, untill the Node becomes the left child of the parent.
- If Parent becomes NULL then return NULL, else return the parent

For Example: 1. In-order successor of 35 is 40 because 35 is itself the left child 2. In-order successor of 20 will be 30. - Parent of 20 is 15, but 20 is the right child of 15 so move to the parent (i.e 15). - Parent of 15 is 30 and 15 is the left child of 30 so return 30. 3. In-order successor of 50 will be NULL. - Parent of 50 is 43 and 50 is the right child of 43. So move to the parent - Parent of 43 is 30 and 43 is also the right child of 30. So move to the parent - Parent of 30 is NULL, so return NULL. (i.e 50, does not have an in-order successor)

**Code:**

// Returns the in-order successor of node pointed to by d Node* successor(Node * d) { if(d == NULL) return NULL; // If d has a Right Child if(d->rptr != NULL) { // Move to Right Node d = d->rptr; // Move to the extreme left while(d->lptr != NULL) d = d->lptr; return d; } while(d) { Node* p = d->parent; if(p == NULL) break; if(p->lptr == d) return p; else d = p; } return NULL; }

Let me know your Comments / Feedback / suggestions.

——————————————————————————————-