Miscellaneous

1. Cousins in Binary Tree (LeetCode #993)

1. Problem Description The problem "Cousins in Binary Tree" is given a binary tree and two nodes of the tree, determine if the two nodes are cousins. Two nodes are cousins if they have the same depth but different parents.

LeetCode Link: https://leetcode.com/problems/cousins-in-binary-tree/

1. Optimized Java Code with Detailed Comments

// Definition for TreeNode
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    // Variables to store depth and parent of the first node
    int depthX;
    TreeNode parentX;
    
    // Variables to store depth and parent of the second node
    int depthY;
    TreeNode parentY;

    public boolean isCousins(TreeNode root, int x, int y) {
        // DFS to find the depth and parent of each node
        dfs(root, null, 0, x, y);
        
        // Check if the nodes have the same depth but different parents
        return depthX == depthY && parentX != parentY;
    }
    
    private void dfs(TreeNode node, TreeNode parent, int depth, int x, int y) {
        // Base case: if the node is null
        if (node == null) {
            return;
        }
        
        // Check if current node is either x or y
        if (node.val == x) {
            depthX = depth;
            parentX = parent;
        } else if (node.val == y) {
            depthY = depth;
            parentY = parent;
        }
        
        // Recursively traverse left and right sub-trees
        dfs(node.left, node, depth + 1, x, y);
        dfs(node.right, node, depth + 1, x, y);
    }
}

1. Detailed Algorithm Explanation and Thought Process

The problem asks us to determine if two given nodes in a binary tree are cousins. Two nodes are considered cousins if they are at the same depth but have different parents.

To solve this problem, we can use a Depth-First Search (DFS) approach to traverse the binary tree. During the traversal, we will keep track of the depth and parent of each node. If we find the target nodes, we will store their respective depths and parents.

Here are the steps to approach this problem:

• Create a helper function dfs that takes the current node, its parent, the current depth, and the target nodes x and y as parameters.

• In the dfs function:

  • Check if the current node is either x or y. If it is, store the depth and parent accordingly.

  • Recursively call the dfs function for the left child of the current node, passing the current node as the parent, and the depth incremented by 1.

  • Recursively call the dfs function for the right child of the current node, passing the current node as the parent, and the depth incremented by 1.

• After the DFS traversal, check if the depths of the two target nodes are equal and their parents are different. If both conditions are true, return true. Otherwise, return false.

During the interview process, you can explain the algorithm step by step to the interviewer and discuss its time and space complexity:

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

• Space Complexity: The space complexity is O(h), where h is the height of the tree. In the worst case, when the tree is skewed, the space complexity becomes O(n). However, in a balanced binary tree, the space complexity is O(log n).

2. Diameter of Binary Tree (LeetCode #543)

1. The problem: Diameter of Binary Tree (LeetCode #543)

   • Problem link: https://leetcode.com/problems/diameter-of-binary-tree/

2. Optimized Java code for the problem "Diameter of Binary Tree (LeetCode #543)":

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    int maxDiameter = 0;
    
    public int diameterOfBinaryTree(TreeNode root) {
        calculateDiameter(root);
        return maxDiameter;
    }
    
    private int calculateDiameter(TreeNode node) {
        if (node == null) {
            return 0;
        }
        
        int leftHeight = calculateDiameter(node.left);
        int rightHeight = calculateDiameter(node.right);
        
        maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
        
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

1. Algorithm and approach for solving the problem in an interview:

   • The problem asks us to find the diameter of a binary tree, which is defined as the length of the longest path between any two nodes in the tree.

   • During an interview, it is important to clearly understand the problem statement and constraints. In this case, we need to work with a binary tree and find the longest path between two nodes.

   • We can approach this problem by using a recursive solution. We will create a helper method called calculateDiameter() that calculates the height of each node while also updating the maxDiameter variable.

   • The height of each node is calculated using a depth-first search by recursively calling the calculateDiameter() method on the left and right child nodes.

   • In the helper method, we check if the current node is null. If it is, we return 0 as the height. This is the base case of our recursion.

   • We calculate the heights of the left and right subtrees recursively.

   • We update the maxDiameter variable by comparing it with the sum of left and right subtree heights.

   • Finally, we return the maximum height between the left and right subtrees plus 1, which represents the height of the current node.

   • In the main method, we simply call the calculateDiameter() method on the root node and return the value of maxDiameter.

   • This recursive approach is efficient because it calculates the height of each node only once and updates the maxDiameter variable whenever a longer path is found.

   • By understanding the problem, analyzing the requirements, and implementing the algorithm, we have successfully solved the Diameter of Binary Tree problem on LeetCode.

3. Binary Tree Pruning (LeetCode #814)

1. Problem Description: The problem "Binary Tree Pruning" states that given the root of a binary tree, we need to prune the tree so that every subtree of the tree contains at least one node with a value of 1. Pruning a node means removing any subtree rooted at that node. We need to return the resulting tree after pruning.

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

2. Java Code for "Binary Tree Pruning":

   // Definition for a binary tree node.
   class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
   
       TreeNode(int val) {
           this.val = val;
       }
   }
   
   class Solution {
       public TreeNode pruneTree(TreeNode root) {
           // Base case: if root is null, return null
           if (root == null) {
               return null;
           }
           // Recursively prune left and right subtrees
           root.left = pruneTree(root.left);
           root.right = pruneTree(root.right);
           // If both left and right subtrees are pruned and root has a value of 0, prune the root as well
           if (root.left == null && root.right == null && root.val == 0) {
               return null;
           }
           // Return the pruned tree
           return root;
       }
   }

3. Detailed Algorithm and Explanation:

   • The problem requires us to prune the binary tree in such a way that every subtree contains at least one node with a value of 1.

   • The idea is to perform a post-order traversal on the tree to recursively prune the left and right subtrees.

   • At each node:

     • Recursively prune the left subtree by making the left child the result of the pruneTree() function called on the left child.

     • Recursively prune the right subtree by making the right child the result of the pruneTree() function called on the right child.

   • After pruning the subtrees, we check if both the left and right subtrees are null, and the value of the current node is 0. If this condition is true, it means that all the nodes in the subtree have a value of 0, so we prune this subtree by returning null.

   • Finally, we return the pruned tree.

   During an interview, it's important to discuss the algorithm and thought process step-by-step. Mentioning the base case of null root, performing the post-order traversal, and checking if a subtree needs to be pruned are essential aspects to explain. Additionally, discussing the time and space complexity of the solution can showcase your understanding of the problem.

4. Count Complete Tree Nodes (LeetCode #222)

1. Problem Description: The problem "Count Complete Tree Nodes" on LeetCode (#222) asks us to count the total number of nodes in a complete binary tree. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

   Link to the problem: Count Complete Tree Nodes
2. Optimized Java Code:

/**
 * Definition for a binary tree node.
 * public 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 int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int leftHeight = getLeftHeight(root) + 1; // Adding 1 for the root node
        int rightHeight = getRightHeight(root) + 1; // Adding 1 for the root node
        
        // If the left and right heights are equal, the tree is a perfect binary tree,
        // so we can return the count using the formula: 2^h - 1, where h is the height
        if (leftHeight == rightHeight) {
            return (int) Math.pow(2, leftHeight) - 1;
        }
        
        // If the heights are not equal, the tree is not a perfect binary tree.
        // In this case, we recursively count the nodes in the left and right subtrees and add 1 for the root.
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
    
    private int getLeftHeight(TreeNode node) {
        int height = 0;
        while (node.left != null) {
            height++;
            node = node.left;
        }
        return height;
    }
    
    private int getRightHeight(TreeNode node) {
        int height = 0;
        while (node.right != null) {
            height++;
            node = node.right;
        }
        return height;
    }
}

1. Description and Approach:

   The problem asks us to count the total number of nodes in a complete binary tree. To solve this problem, we can follow a recursive approach.

   • First, we check if the root node is null. If it is, then the tree is empty, so we return 0.

   • Next, we calculate the heights of the left and right subtrees. For this, we define two helper functions getLeftHeight() and getRightHeight(). These functions traverse to the leftmost and rightmost nodes of the tree respectively and count the levels.

   • If both the left and right heights are equal, then the tree is a perfect binary tree. In this case, we can calculate the count using the formula: 2^h - 1, where h is the height of the tree.

   • If the heights are not equal, then the tree is not a perfect binary tree. In this case, we recursively count the nodes in the left and right subtrees and add 1 for the root node.

   • We continue the recursion until we reach the leaf nodes or the tree becomes empty.

   During the interview process, it is important to explain the logic and approach clearly to the interviewer. Additionally, mentioning the time and space complexity of the solution will showcase your understanding of the problem. In this case, the time complexity of the solution is O(log n * log n) and the space complexity is O(log n), where n is the total number of nodes in the tree.

5. Find Leaves of Binary Tree (LeetCode #366)

Problem: The problem "Find Leaves of Binary Tree" asks us to remove all the leaf nodes from a given binary tree and return them as a list of lists in the order of their depths. A leaf node is a node that does not have any children.

LeetCode Link: Find Leaves of Binary Tree

Algorithm: To solve this problem, we can make use of a recursive algorithm. We start by traversing the tree from the bottom up. We can do this by recursively calling a helper function that returns the depth of each node.

In the helper function:

1. If the current node is null, we return -1 to signify that we are at a leaf node.

2. We recursively call the helper function for the left and right children of the current node.

3. We calculate the current depth as 1 + the maximum of the depths of the left and right children.

4. We add the current node to the list of nodes at the current depth.

After the helper function returns, we can remove the leaf nodes from the tree by setting their left and right pointers to null. Finally, we return the list of lists containing the nodes at each depth.

Detailed Java Code:

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        
        helper(root, result);
        
        return result;
    }
    
    private int helper(TreeNode node, List<List<Integer>> result) {
        // Base case: if current node is null, return -1
        if (node == null) {
            return -1;
        }
        
        // Calculate the depths of the left and right children
        int leftDepth = helper(node.left, result);
        int rightDepth = helper(node.right, result);
        
        // Calculate the current depth as 1 + max(leftDepth, rightDepth)
        int currentDepth = 1 + Math.max(leftDepth, rightDepth);
        
        // If the current depth is equal to the size of result list, create a new list
        if (currentDepth == result.size()) {
            result.add(new ArrayList<>());
        }
        
        // Add the current node to the list of nodes at the current depth
        result.get(currentDepth).add(node.val);
        
        // Remove the leaf node by setting its left and right pointers to null
        node.left = null;
        node.right = null;
        
        // Return the current depth
        return currentDepth;
    }
}

During an interview, here are some key points to think through for this problem:

1. Understand the problem statement and clarify any doubts with the interviewer.

2. Discuss the possible approaches and their time and space complexities.

3. Consider edge cases, such as an empty tree or a tree with only a root node.

4. Explain the algorithm step-by-step, emphasizing on recursion and the bottom-up approach.

5. Implement the solution in a clean and concise manner, adding comments to explain the code logic.

6. Test the solution with different test cases to ensure correctness.

By following these steps and demonstrating a good understanding of the problem and its solution, you can showcase your problem-solving skills and algorithmic thinking during the interview process.