Manipulation and Modification

1. Invert Binary Tree (LeetCode #226)

1. Problem Description: The problem "Invert Binary Tree" asks us to invert a binary tree. This means that for every node in the given binary tree, we need to swap its left and right children.

Problem Link: https://leetcode.com/problems/invert-binary-tree/

1. Optimized Java Code: Here's the optimized Java code for solving the "Invert Binary Tree" problem:

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        
        // Swap the left and right subtrees of the current node
        TreeNode temp = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(temp);
        
        return root;
    }
}

1. Algorithm Description: The algorithm for inverting a binary tree recursively can be described as follows:

• The base case of the recursion occurs when we reach a leaf node, i.e., a node that has no children (left and right both are null). In this case, we simply return the leaf node itself.

• For all other nodes, we swap their left and right children recursively. This is done by swapping the left and right subtrees of the current node.

• The recursion continues until all nodes have been visited and inverted.

• Finally, we return the root node of the inverted binary tree.

Thinking through the Algorithm during an Interview: When faced with this problem in an interview, it is important to understand the recursive nature of the solution. Here's how you can think through the algorithm:

1. Understand the base case:

   • Recognize that a leaf node should be returned as it is since it already has no children.

   • Think about what happens when you reach a leaf node and return it.

2. Visualize the recursion:

   • Visualize how the inversion happens by swapping the left and right children of a node.

   • Think about the effect of recursively swapping the left and right subtrees at each node.

3. Handle the null case:

   • Consider how the algorithm should handle the case when the input binary tree is empty (i.e., a null root).

   • Think about the base case and how it handles null inputs.

4. Return the final result:

   • Identify what the final result should be, i.e., the root node of the inverted binary tree.

   • Plan the return statement and understand how the recursion provides the expected result.

By following these steps, you can better understand and explain the algorithm for inverting a binary tree during an interview. Remember to communicate your thought process effectively and consider edge cases.

2. Flatten Binary Tree to Linked List (LeetCode #114)

1. Problem Description: Given a binary tree, flatten it to a linked list in-place. The flattened tree should follow the preorder traversal of the original tree.

LeetCode Problem Link: https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

1. Optimized Java Code:

class Solution {
    public void flatten(TreeNode root) {
        if (root == null)
            return;

        // Store the right subtree in a temporary variable
        TreeNode temp = root.right;

        // Flatten the left subtree
        flatten(root.left);

        // Move the flattened left subtree to the right side of the root
        root.right = root.left;
        root.left = null;

        // Traverse to the end of the modified right subtree
        TreeNode curr = root;
        while (curr.right != null)
            curr = curr.right;

        // Attach the temporary right subtree at the end of the modified right subtree
        curr.right = temp;

        // Flatten the remaining right subtree (if any)
        flatten(temp);
    }
}

1. Algorithm & Interview Process Explanation:

In this problem, we are given a binary tree and we need to flatten it to a linked list in-place. The flattened tree should follow the preorder traversal of the original tree.

To solve this problem, we can use a recursive approach. The main idea is to flatten the left subtree, then move the flattened left subtree to the right side of the root, and finally flatten the remaining right subtree (if any).

Here is how the algorithm works:

• Start by checking if the root is null. If it is, simply return.

• If the root has a left subtree, recursively apply the flatten function on the left subtree to flatten it.

• After flattening the left subtree, store the right subtree in a temporary variable.

• Move the flattened left subtree to the right side of the root by setting root.right = root.left and root.left = null.

• Traverse to the end of the modified right subtree by using a while loop. The end of the modified right subtree will be the rightmost node.

• Attach the temporary right subtree at the end of the modified right subtree by setting curr.right = temp.

• Finally, recursively apply the flatten function on the remaining right subtree (if any) to flatten it.

During an interview, you can explain this algorithm step by step and mention that it uses a recursive approach to flatten the binary tree in place. The key steps are to flatten the left subtree, move the flattened left subtree to the right side of the root, and then continue to flatten the remaining right subtree. Additionally, it is important to mention that the algorithm follows a preorder traversal order.

You can also discuss the time and space complexity of the algorithm:

• Time Complexity: The algorithm visits each node once, so the time complexity is O(N), where N is the number of nodes in the binary tree.

• Space Complexity: The space complexity is O(1) since the algorithm is performed in-place and does not use any extra space except for the recursive function stack. In the worst case, the maximum depth of the recursive function stack would be the height of the binary tree, resulting in O(log N) space complexity.

3. Recover Binary Search Tree (LeetCode #99)

1. Problem Description: The problem "Recover Binary Search Tree" on LeetCode, represented by problem number #99, involves recovering a binary search tree where two of its elements have been swapped. The task is to restore the original BST structure.

Problem Link: https://leetcode.com/problems/recover-binary-search-tree/

1. Java Code for "Recover Binary Search Tree":

public class Solution {
    TreeNode firstElement = null;
    TreeNode secondElement = null;
    TreeNode prevElement = new TreeNode(Integer.MIN_VALUE);
    
    public void recoverTree(TreeNode root) {
        // In-order traversal to find the two swapped elements
        traverse(root);
        
        // Swap the two elements
        int temp = firstElement.val;
        firstElement.val = secondElement.val;
        secondElement.val = temp;
    }
    
    private void traverse(TreeNode root) {
        if (root == null)
            return;
        
        traverse(root.left);
        
        // Check if current element is misplaced
        if (firstElement == null && prevElement.val >= root.val)
            firstElement = prevElement;
        
        if (firstElement != null && prevElement.val >= root.val)
            secondElement = root;
        
        prevElement = root;
        
        traverse(root.right);
    }
}

Detailed Comments are added within the code to explain each step.

1. Algorithmic Thinking Process:

• The problem statement states that two elements in a binary search tree (BST) have been swapped.

• To solve this problem, we can utilize the property of a BST, which is that the inorder traversal of a BST is always sorted in ascending order.

• So, our approach will be to perform an inorder traversal of the given tree, keep track of the previous element visited.

• During the traversal, if we encounter two misplaced elements, we will mark them.

• After the traversal, we will swap the values of the misplaced elements, restoring the BST structure.

The algorithm can be summarized as follows:

• Initialize three pointers: firstElement, secondElement, and prevElement.

• Perform an inorder traversal of the given binary search tree.

• During the traversal, check if the current element and the previous element are misplaced.

• If the firstElement is not set (null) and the prevElement is greater than the current element, set firstElement to the previous element.

• If the firstElement is set, and the prevElement is greater than the current element, set secondElement to the current element.

• After the traversal, swap the values of the firstElement and secondElement.

• The BST is now restored.

During an interview, it is essential to discuss this thinking process with the interviewer. Explain your observations about BST and the reasoning behind using an inorder traversal. Analyze the time and space complexity of the solution and discuss alternative approaches if time permits.

4. Delete Node in a BST (LeetCode #450)

1. Problem description: The problem "Delete Node in a BST" asks us to delete a node with a given value from a given binary search tree while maintaining the structure of the BST. We are required to return the updated BST after deletion.

LeetCode link: https://leetcode.com/problems/delete-node-in-a-bst/

1. Optimized Java code for "Delete Node in a BST" (LeetCode #450) with detailed comments:

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) { // If tree is empty, return null
            return null;
        }
        
        if (key < root.val) { // Key is less than current node's value, move to left subtree
            root.left = deleteNode(root.left, key);
        } else if (key > root.val) { // Key is greater than current node's value, move to right subtree
            root.right = deleteNode(root.right, key);
        } else { // Key is equal to current node's value, found the node to delete
            if (root.left == null) { // If left subtree is null, return right subtree
                return root.right;
            } else if (root.right == null) { // If right subtree is null, return left subtree
                return root.left;
            }
            
            // Both left and right subtrees are not null
            // Find the minimum value in the right subtree (smallest value greater than current node)
            TreeNode minNode = findMin(root.right);
            root.val = minNode.val; // Replace the current node's value with minNode's value
            root.right = deleteNode(root.right, minNode.val); // Delete minNode from right subtree
        }
        
        return root; // Return the updated BST
    }
    
    // Helper function to find the minimum value node in a BST (leftmost node)
    private TreeNode findMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}

1. Detailed description of the algorithm and thought process during an interview:

• In order to delete a node from the BST, we need to handle three cases:

  1. If the key to delete is less than the value of the current node, we recursively call the delete function on the left subtree of the current node.

  2. If the key to delete is greater than the value of the current node, we recursively call the delete function on the right subtree of the current node.

  3. If the key to delete is equal to the value of the current node, we have found the node to delete.

     • If the current node doesn't have a left subtree, we replace the current node with its right subtree. This handles the case when the node to delete is a leaf or has only a right child.

     • If the current node doesn't have a right subtree, we replace the current node with its left subtree. This handles the case when the node to delete has only a left child.

     • If the current node has both left and right subtrees, we find the minimum value node from the right subtree (smallest value greater than the current node). We replace the current node's value with the value of the minimum node, and then recursively call the delete function on the right subtree to delete the minimum node.

• The implementation uses a helper function findMin to find the minimum value node in a BST (which is the leftmost node).

• During an interview, it's important to communicate your approach and thought process clearly to the interviewer. Explain the steps and cases involved in deleting a node from the BST. Start by analyzing the current node's value with the key to delete and explain the three cases. Discuss the implementation details like the use of recursion and the helper function. Finally, explain the runtime complexity and briefly mention any edge cases or optimizations that could be applied.

5. Trim a Binary Search Tree (LeetCode #669)

1. Problem Description: The problem "Trim a Binary Search Tree" is described as follows:

Given the root of a binary search tree and two integers low and high, trim the tree such that all elements in the tree are between low and high (inclusive). Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node's descendant should remain the same, but the node itself may be removed).

Problem Link: Trim a Binary Search Tree (LeetCode #669)

1. Optimized Java Code with Detailed Comments:

// Definition for a binary tree node.
// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode() {}
//     TreeNode(int val) { this.val = val; }
//     TreeNode(int val, TreeNode left, TreeNode right) {
//         this.val = val;
//         this.left = left;
//         this.right = right;
//     }
// }

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }
        
        // If current node's value is less than low, trim the left subtree
        if (root.val < low) {
            return trimBST(root.right, low, high);
        }
        
        // If current node's value is greater than high, trim the right subtree
        if (root.val > high) {
            return trimBST(root.left, low, high);
        }
        
        // Trim left and right subtrees recursively
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        
        return root;
    }
}

1. Detailed Description & Algorithm:

The problem asks us to trim a binary search tree such that all elements in the tree are between the given range [low, high]. Trimming the tree means removing any nodes whose values are outside the range, but all the descendants of a trimmed node should still be contained in the resulting tree.

To solve this problem efficiently, we can use a recursive approach. Here's a step-by-step explanation:

• Firstly, we handle the base case. If the current node is null (i.e., we have reached a leaf node or an empty tree), we return null since there is nothing to trim.

• Next, we compare the value of the current node with the given range [low, high].

  • If the current node's value is less than the low range, it means that all nodes in the left subtree will also be less than the low range. Therefore, we recursively trim the right subtree by calling the trimBST() function on the right child of the current node, and return the result.

  • If the current node's value is greater than the high range, it means that all nodes in the right subtree will also be greater than the high range. Therefore, we recursively trim the left subtree by calling the trimBST() function on the left child of the current node, and return the result.

• If the current node's value is within the given range, it means that the current node should be included in the trimmed tree. In this case, we recursively trim both the left and right subtrees by calling the trimBST() function on the left and right children of the current node, respectively.

• Finally, we update the left and right children of the current node with the trimmed left and right subtrees, and return the current node as the root of the trimmed tree.

This recursive approach ensures that we traverse the entire tree efficiently and trim it as required. The algorithm has a time complexity of O(N), where N is the number of nodes in the tree, as we need to visit every node once.

During an interview, it's important to understand the problem requirements and constraints, as well as the data structures involved (in this case, a binary search tree). You can discuss the constraints of the problem with the interviewer and confirm your understanding before proceeding to the implementation. Explaining the algorithm step by step and discussing the time and space complexity can also demonstrate your problem-solving and analytical skills.