/******************************************************************************
* File: InplaceTreeDelete.hh
* Author: Keith Schwarz (htiek@cs.stanford.edu)
*
* An O(n)-time, O(1)-space algorithm for freeing all of the nodes in a binary
* search tree.
*
* In languages like C or C++ with explicit memory management, all memory
* allocated for a data structure must be explicitly freed.  When working with
* information about where all of the nodes in a structure live.
*
* The algorithm contained here is an O(n)-time, O(1)-space algorithm for
* freeing all of the nodes in a binary search tree with n nodes.  Its overhead
* is purely limited to the stack space required to hold a single stack frame
* with a constant number of pointers.
*
* Intuitively, the algorithm is an optimization of an inorder algorithm that
* deletes all the nodes of the tree in the order in which they would be
* visited by an inorder traversal.  This is unusual; most algorithms for
* deleting trees use a postorder traversal so that no node is deleted until
* all of its children have been freed.
*
* Intuitively, the algorithm works by getting a tree like this one:
*
*                      Root
*                     /    \
*                 Left     Right
*                Subtree  Subtree
*
* Then recursively freeing the left subtree, then the root, then the right
* subtree.  An initial implementation of this algorithm is given here:
*
*     void DeleteTreeRec(Node* root) {
*         if (root == nullptr) return;
*
*         // Free the left subtree
*         DeleteTreeRec(root->left);
*
*         // Cache a pointer to the right subtree.
*         Node* toDelete = root->right;
*
*         // Delete the root.
*         delete root;
*
*         // Recursively delete the right subtree.
*         DeleteTreeRec(toDelete);
*    }
*
* This approach will successfully delete the entire tree, but its space usage
* is not very good.  The number of stack frames active at any one point in
* time can equal the height of the tree, so the space usage is O(h).  In the
* worst-case, this gives a space usage of O(n) for a degenerate tree, which
* will almost certainly cause a stack overflow.
*
* To address this, we will use a clever trick first I first heard from Leonid
* Shamis (and have not seen documented elsewhere).  The idea is to delete the
* nodes of the tree in the same order in which they would have been deleted by
* this recursive algorithm, but to do so without needing extra stack frames.
*
* The main trick used in this construction is the following observation: if
* the root of the tree has no left child, then the algorithm would just delete
* the root, then recursively delete all the nodes from the right subtree.
* This is shown here:
*
*                      Root        <--- Delete this node, ...
*                        \
*                       Right      <--- ... then recursively delete this
*                      Subtree              subtree.
*
* Consequently, if we can somehow reshape the tree so that we get it into this
* configuration, we can very easily remove one node from the tree.
*
* To accomplish this, we will use a series of tree rotations to rearrange the
* nodes in a tree.  Recall that a right rotation is a transformation of a BST
* that is done as follows:
*
*              u                v
*             / \              / \
*            v   C    --->    A   u
*           / \                  / \
*          A   B                B   C
*
* This structural transformation preserves the relative ordering of the nodes
* in the tree (in that an inorder traversal of the tree before and after the
* rotation will produce the same sequence of nodes), but decreases the height
* of the left subtree of the tree by one.  In fact, applying sufficiently
* many right rotations to the root of a tree will eventually place the
* leftmost tree node at the root of the tree with no left child.
*
* Based on this observation, the algorithm we will use to free a tree in O(1)
* auxiliary storage space is the following:
*
*    1. If the tree root is NULL, we are done.
*    2. If the tree root has a left child, apply a left rotation.
*    3. If the tree root has no left child, delete the root and make its right
*          child the root of the tree.
*    4. Go to (1)
*
* How does this algorithm follow from our original inorder deletion algorithm?
* The reason for this is the order in which the nodes in the tree are deleted.
* We claim that the nodes in the tree will be deleted by both the recursive
* and the in-place algorithms in the same order.  The proof is done by an
* induction on the height of the left subtree.
*
* As our base case, if the tree is empty (height -1), then both of these
* algorithms will not delete any nodes.  If the tree is just a single node
* (height 0), then both of the algorithms will immediately delete the root and
* do no other deletions.
*
* For the inductive step, suppose that we have a tree consisting of a root v
* node with a left subtree L and a right subtree R.  Suppose that the height
* of this new tree is h + 1, meaning that the heights of L and R are both at
* most h.  This means that our tree looks like this:
*
*                                 v
*                                / \
*                               L   R
*
* There are two cases to consider.  First, if L is empty, then the recursive
* algorithm will recurse on L (making no deletions), then delete v, then
* delete the nodes in R.  The in-place algorithm will delete v, then delete
* all the nodes in R.  By our inductive hypothesis, the deletion of the nodes
* in R will be done the same way by both of the algorithms, so in this case
* both of the algorithms delete the nodes in the same order.
*
* Second, if L is nonempty, then it must consist of a root u with two subtrees
* A and B.  Since L has height at most h, A and B have heights at most h - 1.
* This is shown here:
*
*                                 v
*                                / \
*                               u   R
*                              / \
*                             A   B
*
* The recursive algorithm will first recurse on the subtree rooted at U.  It
* then deletes all the nodes in A, then the node u, then all the nodes in B.
* Then, it deletes v, then the nodes in R.  The deletion order is therefore
* A, u, B, v, R.
*
* The in-place algorithm will do a right rotation to reshape the tree into
* this tree here:
*
*              u                v
*             / \              / \
*            v   R    --->    A   u
*           / \    &nb C++ Pretty Print /******************************************************************************
* File: InplaceTreeDelete.hh
* Author: Keith Schwarz (htiek@cs.stanford.edu)
*
* An O(n)-time, O(1)-space algorithm for freeing all of the nodes in a binary
* search tree.
*
* In languages like C or C++ with explicit memory management, all memory
* allocated for a data structure must be explicitly freed.  When working with
* information about where all of the nodes in a structure live.
*
* The algorithm contained here is an O(n)-time, O(1)-space algorithm for
* freeing all of the nodes in a binary search tree with n nodes.  Its overhead
* is purely limited to the stack space required to hold a single stack frame
* with a constant number of pointers.
*
* Intuitively, the algorithm is an optimization of an inorder algorithm that
* deletes all the nodes of the tree in the order in which they would be
* visited by an inorder traversal.  This is unusual; most algorithms for
* deleting trees use a postorder traversal so that no node is deleted until
* all of its children have been freed.
*
* Intuitively, the algorithm works by getting a tree like this one:
*
*                      Root
*                     /    \
*                 Left     Right
*                Subtree  Subtree
*
* Then recursively freeing the left subtree, then the root, then the right
* subtree.  An initial implementation of this algorithm is given here:
*
*     void DeleteTreeRec(Node* root) {
*         if (root == nullptr) return;
*
*         // Free the left subtree
*         DeleteTreeRec(root->left);
*
*         // Cache a pointer to the right subtree.
*         Node* toDelete = root->right;
*
*         // Delete the root.
*         delete root;
*
*         // Recursively delete the right subtree.
*         DeleteTreeRec(root->right);
*    }
*
* This approach will successfully delete the entire tree, but its space usage
* is not very good.  The number of stack frames active at any one point in
* time can equal the height of the tree, so the space usage is O(h).  In the
* worst-case, this gives a space usage of O(n) for a degenerate tree, which
* will almost certainly cause a stack overflow.
*
* To address this, we will use a clever trick first I first heard from Leonid
* Shamis (and have not seen documented elsewhere).  The idea is to delete the
* nodes of the tree in the same order in which they would have been deleted by
* this recursive algorithm, but to do so without needing extra stack frames.
*
* The main trick used in this construction is the following observation: if
* the root of the tree has no left child, then the algorithm would just delete
* the root, then recursively delete all the nodes from the right subtree.
* This is shown here:
*
*                      Root        <--- Delete this node, ...
*                        \
*                       Right      <--- ... then recursively delete this
*                      Subtree              subtree.
*
* Consequently, if we can somehow reshape the tree so that we get it into this
* configuration, we can very easily remove one node from the tree.
*
* To accomplish this, we will use a series of tree rotations to rearrange the
* nodes in a tree.  Recall that a right rotation is a transformation of a BST
* that is done as follows:
*
*              u                v
*             / \              / \
*            v   C    --->    A   u
*           / \                  / \
*          A   B                B   C
*
* This structural transformation preserves the relative ordering of the nodes
* in the tree (in that an inorder traversal of the tree before and after the
* rotation will produce the same sequence of nodes), but decreases the height
* of the left subtree of the tree by one.  In fact, applying sufficiently
* many right rotations to the root of a tree will eventually place the
* leftmost tree node at the root of the tree with no left child.
*
* Based on this observation, the algorithm we will use to free a tree in O(1)
* auxiliary storage space is the following:
*
*    1. If the tree root is NULL, we are done.
*    2. If the tree root has a left child, apply a left rotation.
*    3. If the tree root has no left child, delete the root and make its right
*          child the root of the tree.
*    4. Go to (1)
*
* How does this algorithm follow from our original inorder deletion algorithm?
* The reason for this is the order in which the nodes in the tree are deleted.
* We claim that the nodes in the tree will be deleted by both the recursive
* and the in-place algorithms in the same order.  The proof is done by an
* induction on the height of the left subtree.
*
* As our base case, if the tree is empty (height -1), then both of these
* algorithms will not delete any nodes.  If the tree is just a single node
* (height 0), then both of the algorithms will immediately delete the root and
* do no other deletions.
*
* For the inductive step, suppose that we have a tree consisting of a root v
* node with a left subtree L and a right subtree R.  Suppose that the height
* of this new tree is h + 1, meaning that the heights of L and R are both at
* most h.  This means that our tree looks like this:
*
*                                 v
*                                / \
*                               L   R
*
* There are two cases to consider.  First, if L is empty, then the recursive
* algorithm will recurse on L (making no deletions), then delete v, then
* delete the nodes in R.  The in-place algorithm will delete v, then delete
* all the nodes in R.  By our inductive hypothesis, the deletion of the nodes
* in R will be done the same way by both of the algorithms, so in this case
* both of the algorithms delete the nodes in the same order.
*
* Second, if L is nonempty, then it must consist of a root u with two subtrees
* A and B.  Since L has height at most h, A and B have heights at most h - 1.
* This is shown here:
*
*                                 v
*                                / \
*                               u   R
*                              / \
*                             A   B
*
* The recursive algorithm will first recurse on the subtree rooted at U.  It
* then deletes all the nodes in A, then the node u, then all the nodes in B.
* Then, it deletes v, then the nodes in R.  The deletion order is therefore
* A, u, B, v, R.
*
* The in-place algorithm will do a right rotation to reshape the tree into
* this tree here:
*
*              u                v
*             / \              / \
*            v   R    --->    A   u
*           / \                  / \
*          A   B                B   R
*
* Note that the height of the left subtree has decreased by one.  Therefore,
* by our inductive hypothesis, the recursive deletion algorithm will delete
* the nodes in this tree in the same order that the in-place algorithm would
* delete these nodes.  This is in the order A, v, B, u, R.  This matches the
* order in which the nodes in the original tree would be deleted by the
* recursive algorithm, so the claim holds for trees of height h + 1, as
* required.
*
* We have now established that this algorithm deletes the nodes in the tree in
* the same order that they would be deleted by the recursive traversal, and
* thus can be thought of as a space-optimized version of the recursive
* algorithm.  However, we have yet to establish any bounds on the runtime of
* this algorithm.  To do so, we will now prove that the runtime of this
* algorithm is O(n).
*
* First, note that each tree rotation can be done by rearranging a total of
* O(1) pointers, and each deletion is assumed to take O(1) time.  The in-place
* algorithm clearly only does O(n) deletions, since it never deletes the same
* node twice, so we need to put a bound on the number of rotations that this
* algorithm will ever do.
*
* To do this, we will use the fact that the nodes are deleted in the order in
* which the recursive in-order traversal algorithm would make the deletions.
* This means that if we are given a tree with root u and subtrees L and R, we
* know that the algorithm will delete all of the nodes in L, then the node u,
* then the nodes in R.
*
* We need one more key observation: suppose that we are given a tree like the
* one above, which is shown here:
*
*                                 u
*                                / \
*                               L   R
*
* We claim that the edge from u to R is never rotated.  We could formalize
* this using an inductive argument, but the intution is the following: if L
* is empty, then we will delete the node u, and so the edge ceases to exist
* without ever being rotated.  On the other hand, if L is not empty, then
* after doing a rotation, we will end up with this tree:
*
*              u                v
*             / \              / \
*            v   R    --->    A   u
*           / \                  / \
*          A   B                B   R
*
* Since the nodes in this tree are deleted in an in-order fashion, we will
* delete all of A, then delete the node v.  We're now left with a tree with
* an edge from u to R and a smaller left subtree, so inductively we know that
* the edge from u to R is never rotated.
*
* Given this result, we can start to bound the number of rotations that are
* going to be done by looking at the number of rotations necessary to delete
* the left subtree, plus the number of rotations necessary to delete the right
* subtree.  This works because we never have to worry about doing any
* rotations that would change the nodes in R until we've done all of the
* rotations necessary to delete the nodes in L.  For this, we can make a
* simple inductive argument to show that in an n-node tree, at most n - 1
* rotations are made.  (We special-case the case where the tree is empty and
* say that zero rotations are done).
*
* As a base case, if the tree has just one node, zero rotations are done, and
* 0 = 1 - 1.
*
* For the inductive step, assume that the tree has n + 1 nodes in it.  If the
* left subtree is empty, then we delete the root, dropping the number of nodes
* to n.  We then need at most n - 1 more rotations to delete the remaining
* tree (by our IH), and n - 1 = (n + 1) - 2 <= (n + 1) - 1, so the claim
* holds.
*
* On the other hand, if the left subtree isn't empty, then we will do a single
* rotation, as shown here:
*
*              u                v
*             / \              / \
*            v   R    --->    A   u
*           / \                  / \
*          A   B                B   R
*
* Let's think about how many rotations are necessary to delete this tree.
* Since we won't ever rotate the edge from v to u, we can count the number of
* rotations as the number of rotations necessary to delete the nodes in A,
* plus the number of rotations necessary to delete the nodes in the subtree
* rooted at u.  If we denote the number of nodes in a subtree T as #(T), then
* the number of rotations necessary to free this tree is given by #(A) + #(u).
* Note that #(A) + #(u) = n - 1, since every node except v is counted here.
* By the IH, the number of rotations necessary for each step is therefore
* #(A) - 1 + #(u) - 1 = n - 2.  Adding in the one rotation we did in the first
* step, this means that a total of at most n - 1 rotations are necessary, so
* the claim holds in this step.
*
* Overall, this means that the algorithm makes at most O(n) rotations and O(n)
* deletions, and uses only O(1) storage space.  Therefore, the overall
* algorithm takes time O(n) and uses O(1) space.
*/

#ifndef InplaceTreeDelete_Included
#define InplaceTreeDelete_Included

/**
* Function: DeleteTreeInPlace(TreeNode* root,
*                             TreeNode* TreeNode::* left  = &TreeNode::left,
*                             TreeNode* TreeNode::* right = &TreeNode::right);
* Usage: DeleteTreeInPlace(root, &Node::less, &Node::more);
*        DeleteTreeInPlace(root);
* ----------------------------------------------------------------------------
* Deletes all nodes in the tree rooted at root using O(1) storage space and
* O(n) time.  The algorithm will use the member pointers provided as inputs to
* determine which pointers store the left and right subtrees.
*/

template <typename TreeNode>
void DeleteTreeInPlace(TreeNode* root,
TreeNode* TreeNode::* left  = &TreeNode::left,
TreeNode* TreeNode::* right = &TreeNode::right) {
/* Keep deleting nodes while there are nodes to delete. */
while (root != nullptr) {
/* If there is a left child, do a left rotate. */
if (root->*left != nullptr) {
/* Store the root's left child, which will become the new root. */
TreeNode* leftNode = root->*left;

/* Make the left subtree's right subtree the left subtree of the root. */
root->*left = root->*left->*right;

/* Make the new root node have the old root as a right child. */
leftNode->*right = root;

/* Make the root the old left subtree. */
root = leftNode;

}
/* Otherwise, delete the root and descend into the right subtree. */
else {
TreeNode* rightTree = root->*right;
delete root;
root = rightTree;
}
}
}

#endif
sp;             / \
*          A   B                B   R
*
* Note that the height of the left subtree has decreased by one.  Therefore,
* by our inductive hypothesis, the recursive deletion algorithm will delete
* the nodes in this tree in the same order that the in-place algorithm would
* delete these nodes.  This is in the order A, v, B, u, R.  This matches the
* order in which the nodes in the original tree would be deleted by the
* recursive algorithm, so the claim holds for trees of height h + 1, as
* required.
*
* We have now established that this algorithm deletes the nodes in the tree in
* the same order that they would be deleted by the recursive traversal, and
* thus can be thought of as a space-optimized version of the recursive
* algorithm.  However, we have yet to establish any bounds on the runtime of
* this algorithm.  To do so, we will now prove that the runtime of this
* algorithm is O(n).
*
* First, note that each tree rotation can be done by rearranging a total of
* O(1) pointers, and each deletion is assumed to take O(1) time.  The in-place
* algorithm clearly only does O(n) deletions, since it never deletes the same
* node twice, so we need to put a bound on the number of rotations that this
* algorithm will ever do.
*
* To do this, we will use the fact that the nodes are deleted in the order in
* which the recursive in-order traversal algorithm would make the deletions.
* This means that if we are given a tree with root u and subtrees L and R, we
* know that the algorithm will delete all of the nodes in L, then the node u,
* then the nodes in R.
*
* We need one more key observation: suppose that we are given a tree like the
* one above, which is shown here:
*
*                                 u
*                                / \
*                               L   R
*
* We claim that the edge from u to R is never rotated.  We could formalize
* this using an inductive argument, but the intution is the following: if L
* is empty, then we will delete the node u, and so the edge ceases to exist
* without ever being rotated.  On the other hand, if L is not empty, then
* after doing a rotation, we will end up with this tree:
*
*              u                v
*             / \              / \
*            v   R    --->    A   u
*           / \                  / \
*          A   B                B   R
*
* Since the nodes in this tree are deleted in an in-order fashion, we will
* delete all of A, then delete the node v.  We're now left with a tree with
* an edge from u to R and a smaller left subtree, so inductively we know that
* the edge from u to R is never rotated.
*
* Given this result, we can start to bound the number of rotations that are
* going to be done by looking at the number of rotations necessary to delete
* the left subtree, plus the number of rotations necessary to delete the right
* subtree.  This works because we never have to worry about doing any
* rotations that would change the nodes in R until we've done all of the
* rotations necessary to delete the nodes in L.  For this, we can make a
* simple inductive argument to show that in an n-node tree, at most n - 1
* rotations are made.  (We special-case the case where the tree is empty and
* say that zero rotations are done).
*
* As a base case, if the tree has just one node, zero rotations are done, and
* 0 = 1 - 1.
*
* For the inductive step, assume that the tree has n + 1 nodes in it.  If the
* left subtree is empty, then we delete the root, dropping the number of nodes
* to n.  We then need at most n - 1 more rotations to delete the remaining
* tree (by our IH), and n - 1 = (n + 1) - 2 <= (n + 1) - 1, so the claim
* holds.
*
* On the other hand, if the left subtree isn't empty, then we will do a single
* rotation, as shown here:
*
*              u                v
*             / \              / \
*            v   R    --->    A   u
*           / \                  / \
*          A   B                B   R
*
* Let's think about how many rotations are necessary to delete this tree.
* Since we won't ever rotate the edge from v to u, we can count the number of
* rotations as the number of rotations necessary to delete the nodes in A,
* plus the number of rotations necessary to delete the nodes in the subtree
* rooted at u.  If we denote the number of nodes in a subtree T as #(T), then
* the number of rotations necessary to free this tree is given by #(A) + #(u).
* Note that #(A) + #(u) = n - 1, since every node except v is counted here.
* By the IH, the number of rotations necessary for each step is therefore
* #(A) - 1 + #(u) - 1 = n - 2.  Adding in the one rotation we did in the first
* step, this means that a total of at most n - 1 rotations are necessary, so
* the claim holds in this step.
*
* Overall, this means that the algorithm makes at most O(n) rotations and O(n)
* deletions, and uses only O(1) storage space.  Therefore, the overall
* algorithm takes time O(n) and uses O(1) space.
*/

#ifndef InplaceTreeDelete_Included
#define InplaceTreeDelete_Included

/**
* Function: DeleteTreeInPlace(TreeNode* root,
*                             TreeNode* TreeNode::* left  = &TreeNode::left,
*                             TreeNode* TreeNode::* right = &TreeNode::right);
* Usage: DeleteTreeInPlace(root, &Node::less, &Node::more);
*        DeleteTreeInPlace(root);
* ----------------------------------------------------------------------------
* Deletes all nodes in the tree rooted at root using O(1) storage space and
* O(n) time.  The algorithm will use the member pointers provided as inputs to
* determine which pointers store the left and right subtrees.
*/

template <typename TreeNode>
void DeleteTreeInPlace(TreeNode* root,
TreeNode* TreeNode::* left  = &TreeNode::left,
TreeNode* TreeNode::* right = &TreeNode::right) {
/* Keep deleting nodes while there are nodes to delete. */
while (root != nullptr) {
/* If there is a left child, do a left rotate. */
if (root->*left != nullptr) {
/* Store the root's left child, which will become the new root. */
TreeNode* leftNode = root->*left;

/* Make the left subtree's right subtree the left subtree of the root. */
root->*left = root->*left->*right;

/* Make the new root node have the old root as a right child. */
leftNode->*right = root;

/* Make the root the old left subtree. */
root = leftNode;

}
/* Otherwise, delete the root and descend into the right subtree. */
else {
TreeNode* rightTree = root->*right;
delete root;
root = rightTree;
}
}
}

#endif