# Thread: Delete a node in a binary tree

1. ## Delete a node in a binary tree

What the result will be if

9,
2,
5

is delete in the binary tree? (pls see the attach)

for the case 5, will 6 be the upper node?

thk a lot

2. Am I correct?
pls see the attachment, thk

3. 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.

This link might give you a little insight into the algorithms used. Two different methods are described.

Popular pages Recent additions