**Delete (***x***)**

- 1.
- Locate the leaf
*L*containing*x*and let*v*be the parent of*L* - 2.
- Delete
*L*. This may leave*v*with only one child. If*v*is the root, delete*v*and let its lone child become the new root. This reduces the number of levels by 1. If*v*is not the root, let*p*= parent of*v*- If
*p*has a child with 3 children, transfer an appropriate one to*v*if this child is adjacent (sibling) to*v*. - If children of
*p*adjacent to*v*have only two children, transfer the lone child of*v*to an adjacent sibling of*v*and delete*v*.- If
*p*now has only one child, repeat recursively with*p*in place of*v*. The recursion can ripple all the way up to the root, leading to a decrease in the number of levels.

- If

eEL,CSA_Dept,IISc,Bangalore