Delete Leaves With a Given Value

class Solution {
public:
    TreeNode* deleteLeafNodes(TreeNode* root, int target) {
        stack<TreeNode*> nodeStack;
        TreeNode *node = root, *lastProcessedNode = nullptr;

        while (!nodeStack.empty() || node != nullptr) {
            while (node != nullptr) {
                nodeStack.push(node);
                node = node->left;
            }

            node = nodeStack.top();

            if (node->right != lastProcessedNode && node->right) {
                node = node->right;
                continue;  
            }

            nodeStack.pop();

            if (node->right == nullptr && node->left == nullptr && node->val == target) {
                if (nodeStack.empty()) {
                    return nullptr;
                }

                TreeNode* parentNode = nodeStack.top();

                if (parentNode->left == node) {
                    parentNode->left = nullptr;
                } else {
                    parentNode->right = nullptr;
                }
            }

            lastProcessedNode = node;
            node = nullptr;
        }
        return root;
    }
};

This code snippet solves the problem of deleting leaf nodes in a binary tree if they have a specific value. It is written in C++ and utilizes tree traversal with the help of a stack to manage the nodes. Here's a summarized explanation of how the code functions:

• Define a TreeNode class with standard binary tree node attributes left, right, and val.
• Use a stack called nodeStack to keep track of nodes during tree traversal.
• Initialize pointers node to start at the root of the tree and lastProcessedNode to help manage the traversal and track the node processing sequence.
• Use a loop to traverse through the tree. Inner loops handle the navigation to the leftmost child by stacking each node, before checking and potentially moving right.
• After reaching a node and checking it does not have child nodes (indicative of a leaf), check the node's value against the target.
• If the node's value matches the target and it is a leaf, this node needs deletion:
  • If the stack is empty after popping the node, it indicates the root itself was the target leaf, and the tree becomes empty (hence returns nullptr).
  • If not empty, determine whether the node was a left or a right child and set the corresponding parent pointer to nullptr, effectively deleting the node.
• Update lastProcessedNode to the node that was just processed and continue until all nodes are checked.
• Return the modified tree's root. If all operations complete without finding a target leaf node, the original tree (root) is returned unchanged.

This solution provides an efficient means of selectively removing leaf nodes that match a given target value without affecting other nodes in the tree. The approach ensures that the tree's integrity is maintained even as specific nodes are removed.

class Solution {

    public TreeNode pruneLeafNodes(TreeNode treeRoot, int removeVal) {
        Stack<TreeNode> nodesStack = new Stack<>();
        TreeNode activeNode = treeRoot, previousRightNode = null;

        while (!nodesStack.isEmpty() || activeNode != null) {
            while (activeNode != null) {
                nodesStack.push(activeNode);
                activeNode = activeNode.left;
            }

            activeNode = nodesStack.peek();

            if (activeNode.right != previousRightNode && activeNode.right != null) {
                activeNode = activeNode.right;
                continue;
            }

            nodesStack.pop();

            if (activeNode.right == null && activeNode.left == null && activeNode.val == removeVal) {
                if (nodesStack.isEmpty()) {
                    return null;
                }

                TreeNode parentNode = nodesStack.isEmpty() ? null : nodesStack.peek();

                if (parentNode != null) {
                    if (parentNode.left == activeNode) {
                        parentNode.left = null;
                    } else {
                        parentNode.right = null;
                    }
                }
            }

            previousRightNode = activeNode;
            activeNode = null;
        }
        return treeRoot;
    }
}

The given Java solution outlines a method to delete leaf nodes in a binary tree if they hold a specific value. The procedure, implemented in the pruneLeafNodes method of the Solution class, utilizes a stack to manage tree traversal and node deletion without the need for recursion.

Here's how the provided solution handles the task:

1. Initialize a stack to keep track of nodes as you traverse the tree. nodesStack is used for this purpose.
2. Use activeNode to track the current node starting from treeRoot, and previousRightNode to manage backtracking in the binary tree.
3. Enter a loop which continues as long as there are unvisited nodes, handling two major operations:
   • Push left children of the current node to the stack until a leaf is reached.
   • Check if the current node can proceed to the right or needs processing.
4. On reaching a node without unprocessed right children, perform the leaf check and deletion:
   • If a node is a leaf (left and right children are null) and its value matches the target removeVal, determine its relationship to the parent node (kept on top of the stack) and sever this connection, effectively deleting the node.
5. This process cleanses the tree of all leaves matching the target deletion value in a depth-first manner.

This approach ensures:

• Efficiency, as each node is processed exactly once.
• No use of additional data structures other than a stack, keeping memory overhead low.
• The tree's structure is only modified for specific leaf nodes, leaving other nodes intact.

Adopt this strategy in scenarios where selective deletion of leaf nodes based on their value is required, ensuring all nodes are processed in an orderly and efficient manner without recursion, which can be crucial for deep trees or systems with limited stack memory.

class Solution:
    def pruneLeafNodes(self, tree_root: Optional[TreeNode], removal_val: int) -> Optional[TreeNode]:
        if not tree_root:
            return None

        nodes_stack = []
        current = tree_root
        previously_visited = None

        while nodes_stack or current:
            # Navigate to leftmost node
            while current:
                nodes_stack.append(current)
                current = current.left

            # Peek the node at top of the stack without removing
            current = nodes_stack[-1]

            # Process right child if exists and not processed
            if current.right and current.right is not previously_visited:
                current = current.right
                continue  # Continue to leftmost of this subtree

            # Ready to process this node, pop it
            nodes_stack.pop()

            # If node is a lead node and matches removal value
            if not current.right and not current.left and current.val == removal_val:
                if not nodes_stack:
                    return None  # Entire tree is pruned

                # Get parent node
                parent_node = nodes_stack[-1] if nodes_stack else None

                # Detach current node from its parent
                if parent_node and parent_node.left is current:
                    parent_node.left = None
                elif parent_node and parent_node.right is current:
                    parent_node.right = None

            # Mark this node as visited
            previously_visited = current
            # Reset current to None to go back up stack
            current = None

        return tree_root  # Returning possibly pruned tree root

This Python3 program utilizes a class called Solution with the method pruneLeafNodes to remove leaf nodes from a binary tree based on a specific value provided by the user (removal_val). The method modifies the tree structure by strategically navigating through it with a stack, ensuring each node is visited once and process decisions are made at the right time, hence avoiding unnecessary recursion.

Here is a breakdown of how the method operates:

1. Initiate with a check to determine if the tree_root is None; if true, it will return None, indicating an empty tree.

2. Create a nodes_stack to manage the backtrack of nodes and two pointers current and previously_visited initializing with the tree_root and None, respectively.

3. Employ a while loop that continues until all nodes are visited:

   1. Utilize another inner loop to navigate to the leftmost node of the current node and push each traversed node into the stack.

   2. Check if the current node has a right child that hasn't been visited; if true, shift the focus to the right child, effectively heading towards its leftmost subtree.

   3. Process the current node:

      1. Only proceed if the current is a leaf node (has no left or right children) and its value equals removal_val.
      2. If removing this node leaves the stack empty, return None, indicating no nodes left in the tree.
      3. Identify the parent node; if current is the left child, detach it from parent's left and similarly for the right child.

   4. Mark the current node as visited to prevent reprocessing and reset the current node to None, which allows going up the stack to continue processing other nodes.

4. Finally, return tree_root, which may reflect the pruned tree structure, potentially altered if any leaf nodes were the specified value.

This method ensures efficient tree traversal and manipulation using a non-recursive approach, optimizing it for situations where tree recursion could be too deep or stack overflow might be a concern. It respects tree structure integrity at each step, handling each sub-tree only when it’s complete, making it optimal even for large trees.