assuming that one has to delete the root of an AVL tree. Does it matter which node replaces the root, say if it is the next smaller or next greater number than the root itself, as long as the AVL-property is satisfied and the tree is balanced?
Asked
Active
Viewed 30 times
0
-
It doesn't matter whether you choose the predecessor or successor to take the place of the root (barring the edge case of a two-node tree), though depending on the shape of the tree, one choice might require more rotations to maintain AVL structure than the other. – Connor Harris Dec 23 '22 at 16:02
-
@ConnorHarris can one also choose another node (neither the predecessor nor successor) whose value is between the nodes from right and left? – Ozk Dec 23 '22 at 16:08
-
Remember that in a valid binary tree, the root must be greater than or equal to every node in the left subtree and less than or equal to every element in the right subtree, not just the left and right child nodes. – Connor Harris Dec 23 '22 at 16:10