# Thread: Successors and predecessors of a node in binary trees...

1. ## Successors and predecessors of a node in binary trees...

HI,

What are Successors and predecessors of a node in binary trees?

thnx

2. A
|\
BC

I'm not quite sure about these English terms. But if I am correct than A is the predecessor of B and C. And B and C are the successors of A.

3. mmmmmmm but isn't this the same name as to 'parents' and 'children'? A is parent of B and C and B and C are children or child nodes of A ?

4. B and C are the children of A, so A is parent of B and C. I guess successor and predecessor are just other words for child and parent.

5. I am not sure about that, after looking at the code in my book. Maybe u can have a look at the this:
Code:
```/* A binary tree node with parent pointer. */
struct pbin_node {
int data;
struct pbin_node *left;
struct pbin_node *right;
struct pbin_node *parent;
};

/* A binary tree. */
struct pbin_tree {
struct pbin_node *root;
int count;
};

/* Returns the next node in in-order in the tree after X, or NULL if X
is the greatest node in the tree. */
static struct pbin_node *successor(struct pbin_node *x)
{
struct pbin_node *y;

assert(x != NULL);
if (x->right != NULL) {
y = x->right;
while (y->left != NULL)
y = y->left;
}
else {
y = x->parent;
while (y != NULL && x == y->right) {
x = y;
y = y->parent;
}
}

return y;
}```
The function finds the successor of *x.

thnx

6. Found these definitions:

If a node N has a right subtree: The successor of N will be the smallest node in the right subtree of N.

If a node N has no right subtree: If N is a left child, then the next node visited by the in-order traversal will be the parent of N. But what if N is a right child? Then the in-order traversal will keep going up the tree until it gets to a node for which the previous node is a left child.