CODEWITHSUNDEEP
javabinary-search-tree
user2574715
user2574715

Reputation:

How can a node X without right child have a successor?

I have a trouble understanding what's a successor of a node X whenever it doesn't have a right child.

From what I had understood, if a node X had no right child, then it would not have a successor.

But my textbook says the following:

If the right sub-tree of node X is empty and X has a successor Y...

How can X have a successor when it has not right child?

Upvotes: 2

Views: 951

Answers (2)

Manali
Manali

Reputation: 128

The successor of a node X is the smallest greater element S in the tree with respect to X. That is, for all nodes in the set G = { Si | Si > X }, then S is an element of G and S <= Si, for i=1..n.

In a BST, for any node X, all elements in left subtree of X are smaller than X, while all elements in its right subtree are greater than it.

Scenarios

Now consider X as an arbitrary node in your tree, and let P be its parent node. In both of the following cases it does not matter if X has or not a left subtree, which contains elements that are smaller than X.

  1. X has a right subtree

    The successor of X by definition lies in right subtree. The smallest element of the right subtree is the leftmost element, which is the successor of X. If the right subtree contains only one node then that is the successor of X.

  2. X has no right subtree

    1. X is the left child of its parent P

      Then parent P is the successor.

    2. X is a right child of its parent P

      Then the first ancestor of X, lets call it A, such that X falls in the left subtree of A is the successor of X.

Example

        10
       /  \
      5    14
     / \   /  \
    3   7  11  15
   / \  /
   1 4  6

  1. Examples for case 1

    • Successor of 3 is 4 (or, similarly, the successor of 14 is 15)
    • Successor of 10 is 11 (or, similarly, the successor of 5 is 6)

  2. Examples for case 2

    • Successor of 7 is 10 (or, similarly, the successor of 4 is 5)
    • Successor of 11 is 14 (or, similarly, the successor of 6 is 7)

Upvotes: 1

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272667

The successor is simply the next element in the ordered sequence; it doesn't necessarily have to be a child element.

For example, the successor of 5 below is 7:

  7
 / \
5   8

Upvotes: 1

Related Questions