Question

Think about the DELETE(x) operation for a Binary Search Tree with no duplicate elements.

Define the predecessor of a node x as the node whose value immediately precedes x if you sort all the node values in the tree smallest to largest. Define the successor of a node x similarly -- the one "just after" x.

If x has a left child, is the predecessor of x always in x's left sub-tree? If x has a right child, is the successor to x always in x's right sub-tree?

Write a few sentences explaining your reasoning

Answer 1

Q; Define the predecessor of a node x as the node whose value immediately precedes x if you sort all the node values in the tree smallest to largest. Define the successor of a node x similarly -- the one "just after" x.

Ans:

Predecessor and Successor in BST:

After doing inorder traversal of BST we get the sorted output(Asc. order). The neighbor for a given node is called predecessor(the node lies behind of given node) and successor(the node lies ahead of given node).

The predecessor is always the smallest node in the left subtree of a given node.

The successor is always the largest node in the right subtree of a given node.

For example

inorder traversal of BST is 8,10,12,15,16,20,25

if we will find predecessor and successor of 15 then, predecessor of 15 is 12 and successor is 16. it can be easily seen from the inorder traversal of BST.

8 has no predecessor and 25 has no sucessor.

============================================================================================

Q: If x has a left child, is the predecessor of x always in x's left sub-tree? If x has a right child, is the successor to x always in x's right sub-tree?

Ans: yes, the predecessor for given node x will always lie in the x's left sub-tree and successor for a given node x will always lie in the x's right sub-tree.

Reason: predecessor is a value which is less than x and successor is a value which is greater than x. we know in BST, all nodes less than x will be in the left subtree and all nodes greater than x will be in the right subtree.

============================================================================================