The result depends on the algorithm used for removal. After deleting 9 you can be reasonably sure that the resulting tree would be
Code:
5
/ \
2 6
/\ \
1 4 7
/ /
3 8
But for deleting 2, the result could be either
Code:
5
/ \
1 6
\ \
4 7
/ /
3 8
\
9
or
Code:
5
/ \
3 6
/\ \
1 4 7
/
8
\
9
The difference is which direction the replacing node is chosen from. Is it the predecessor or the successor? Deleting 5 will also have different results. Replacing the node with the successor would result in
Code:
6
/ \
2 7
/\ /
1 4 8
/ \
3 9
While replacing the node with the predecessor would give you
Code:
4
/ \
2 6
/\ \
1 3 7
/
8
\
9
Also remember that any removal from a binary search tree must result in a valid binary search tree. In other words, every node's value must be greater than the value in its left node and less than the value in its right node. ![Smile](https://cboard.cprogramming.com/images/smilies/smile.png)
This link might give you a little insight into the algorithms used. Two different methods are described.