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

[Nutshell]

HI,

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

thnx

[Shiro]

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.

[Nutshell]

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 ?

[Shiro]

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.

[Nutshell]

I am not sure about that, after looking at the code in my book. Maybe u can have a look at the this:

/* 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

[Shiro]

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.