Special Trees

1. Complete Binary Tree Inserter (LeetCode #919)

1. The problem "Complete Binary Tree Inserter" can be found on LeetCode at the following link: https://leetcode.com/problems/complete-binary-tree-inserter/

2. Here is the optimized Java code for the "Complete Binary Tree Inserter" problem with detailed comments:

import java.util.LinkedList;
import java.util.Queue;

class CBTInserter {
    private TreeNode root;
    private Queue<TreeNode> queue; // Queue to store all the incomplete nodes
    
    public CBTInserter(TreeNode root) {
        this.root = root;
        this.queue = new LinkedList<>();
        
        // Perform a level order traversal to populate the queue
        // with all the incomplete nodes of the binary tree
        Queue<TreeNode> levelOrderQueue = new LinkedList<>();
        levelOrderQueue.offer(root);
        
        while (!levelOrderQueue.isEmpty()) {
            TreeNode node = levelOrderQueue.poll();
            
            // If the left child is missing, we add it to the queue
            if (node.left == null) {
                queue.offer(node);
            }
            
            // If the right child is missing, we add it to the queue
            if (node.right == null) {
                queue.offer(node);
            }
            
            // Add the children to the level order queue
            if (node.left != null) {
                levelOrderQueue.offer(node.left);
            }
            
            if (node.right != null) {
                levelOrderQueue.offer(node.right);
            }
        }
    }
    
    public int insert(int v) {
        TreeNode node = queue.peek();
        
        // If the left child of the current node is missing, we attach the new node as the left child
        if (node.left == null) {
            node.left = new TreeNode(v);
            queue.offer(node.left);
        }
        
        // If the left child is present but right child is missing, we attach the new node as the right child
        else if (node.right == null) {
            node.right = new TreeNode(v);
            queue.offer(node.right);
            queue.poll(); // The current node is complete, so remove it from the queue
        }
        
        return node.val;
    }
    
    public TreeNode get_root() {
        return root;
    }
}

1. Detailed Description on the Algorithm and Interview Approach:

• In this problem, we are given a completely filled binary tree except for the bottom-most level, which is filled from left to right. We need to design a data structure that supports the following operations:

  • CBTInserter(TreeNode root): Initializes the data structure with the root of the tree.

  • int insert(int v): Inserts a TreeNode with value v into the tree and returns the value of the parent node.

  • TreeNode get_root(): Returns the root node of the tree.

• To implement this functionality efficiently, we will make use of a Queue data structure. The idea is to maintain a queue that stores all the nodes that are missing at least one child. Whenever we insert a new node, we can pop the front node of the queue and attach the new node as its child.

• In the constructor CBTInserter(TreeNode root), we will perform a level-order traversal of the tree and populate the queue with all the incomplete nodes. We can use another queue, levelOrderQueue, to perform the level-order traversal. At each node, we check if the left and right children are missing, and if so, we add the current node to the queue. Additionally, we add the children to the levelOrderQueue for further traversal.

• In the insert(int v) method, we first peek at the front of the queue to get the node that needs a child. If the left child is missing, we create a new node with value v and attach it as the left child. We then add this new node to the queue. If the left child is already present, but the right child is missing, we attach the new node as the right child, add it to the queue, and remove the current node from the queue.

• Finally, the get_root() method returns the root node of the binary tree.

• During an interview, it's important to understand the problem requirements and constraints before starting to code. In this case, understanding the binary tree structure, the types of operations needed, and the need for an efficient solution using a queue can help guide the implementation process.

• While coding, it's a good practice to add comments explaining each step of the algorithm, which can help the interviewer understand your approach.

• Additionally, it's crucial to test the code with various test cases, including edge cases, to ensure that it handles different scenarios correctly.

2. Populating Next Right Pointers in Each Node (LeetCode #116)

1. Problem Description: Populating Next Right Pointers in Each Node (LeetCode #116) You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following structure:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example:

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B.

1. Java Solution with Detailed Comments:

// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};

class Solution {
    public Node connect(Node root) {
        if (root == null) return null;

        // Start with the root node
        Node levelStart = root;

        // Iterate level by level
        while (levelStart.left != null) {
            Node curr = levelStart;

            // Connect nodes on the same level
            while (curr != null) {
                curr.left.next = curr.right;
                if (curr.next != null)
                    curr.right.next = curr.next.left;
                curr = curr.next;
            }

            // Move to the next level
            levelStart = levelStart.left;
        }

        return root;
    }
}

1. Algorithm Explanation:

• The problem is solved using a level-by-level iterative approach.

• We start with the root node and keep track of the start of each level using the levelStart variable.

• For each level, we iterate through all the nodes using the curr variable.

• We connect the left and right child nodes of the current node.

• If the current node has a next node, we connect the right child of the current node to the left child of the next node.

• After connecting all the nodes on the current level, we move to the next level by updating the levelStart variable to its left child.

• We repeat this process until all levels have been processed.

• Finally, we return the root node.

3. Populating Next Right Pointers in Each Node II (LeetCode #117)

1. Problem Description: "Populating Next Right Pointers in Each Node II" is a LeetCode problem #117. The problem asks us to connect each node in a binary tree to its right node, using a special 'next' pointer. The tree may not be a perfect binary tree, so some levels may have empty 'next' pointers. We need to modify the tree in-place, without using any extra space.

Problem Link: https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

1. Optimized Java Code with Detailed Comments:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
}

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return root; // If the root is null, return null
        }
        
        Node levelStart = root;
        
        while (levelStart != null) {
            Node curr = levelStart;
            Node dummy = new Node(0);
            Node prev = dummy;
            
            while (curr != null) {
                if (curr.left != null) {
                    prev.next = curr.left;
                    prev = prev.next;
                }
                
                if (curr.right != null) {
                    prev.next = curr.right;
                    prev = prev.next;
                }
                
                curr = curr.next;
            }
            
            levelStart = dummy.next;
        }
        
        return root;
    }
}

1. Description and Approach:

   • The problem asks us to connect each node in a binary tree to its right node, using the 'next' pointer.

   • We can solve this problem efficiently using the level order traversal approach.

   • In the given solution, we will start from the root and process the tree level by level using two pointers.

   • We maintain the levelStart pointer, which points to the first node of the current level.

   • We have an outer while loop that continues until there are no more levels remaining to process.

   • Inside the outer while loop, we have a curr pointer that points to each node in the current level.

   • We also maintain a dummy node and a prev pointer to build the 'next' connection between nodes in the next level.

   • The inner while loop iterates through the current level and connects the children of the current nodes to the 'next' pointer.

   • We check if the left child exists, then connect it to the 'next' of the previous node, and update the prev pointer.

   • We also check if the right child exists similarly and connect it to the 'next' of the previous node.

   • After completing the inner loop, we move the levelStart pointer one level down.

   • Finally, we return the modified root node.

   • This algorithm has a time complexity of O(N), where N is the total number of nodes in the binary tree, as we have to traverse each node once.

   • It also has a space complexity of O(1) as we are not using any extra space apart from a few pointers.

4. Binary Tree Maximum Path Sum (LeetCode #124)

1. The problem "Binary Tree Maximum Path Sum" can be found on LeetCode at the following link: Binary Tree Maximum Path Sum on LeetCode
2. Here is the optimized Java code for the problem "Binary Tree Maximum Path Sum" with detailed comments:

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

public class Solution {
    int maxValue;

    public int maxPathSum(TreeNode root) {
        // Initialize maxValue to the minimum possible value
        maxValue = Integer.MIN_VALUE;
        
        // Helper function to find the maximum path sum rooted at a particular node
        maxPathSumHelper(root);
        
        // Return the maximum path sum of the binary tree
        return maxValue;
    }
    
    private int maxPathSumHelper(TreeNode node) {
        // Base case: if node is null, return 0
        if (node == null) {
            return 0;
        }
        
        // Recursively find the maximum path sum of the left and right subtree
        int leftSum = Math.max(maxPathSumHelper(node.left), 0);
        int rightSum = Math.max(maxPathSumHelper(node.right), 0);
        
        // Update the maxValue by considering the current node
        maxValue = Math.max(maxValue, node.val + leftSum + rightSum);
        
        // Return the maximum path sum rooted at the current node
        return node.val + Math.max(leftSum, rightSum);
    }
}

1. Description of the algorithm and thought process:

The problem asks us to find the maximum path sum in a binary tree. A path is defined as a sequence of nodes from some starting node to any node in the tree along the parent-child connections. The maximum path sum can include any number of nodes and can start and end at any nodes.

To solve this problem, we can use a recursive approach. We define a helper function maxPathSumHelper() that calculates the maximum path sum rooted at a particular node. The helper function returns the maximum path sum rooted at the current node to be used by its parent node.

In the maxPathSumHelper() function:

• We first check the base case, which is if the current node is null, we return 0.

• Then, we recursively find the maximum path sum of the left and right subtree by calling the maxPathSumHelper() function on the left and right child nodes. We take the maximum of these sums and if any sum is negative, we treat it as 0 because a negative sum will only decrease the overall path sum.

• We update the maxValue variable by considering the current node's value plus the maximum path sums of the left and right subtrees.

• Finally, we return the maximum path sum rooted at the current node to be used by its parent node.

In the maxPathSum() function:

• We initialize the maxValue variable to the minimum possible value.

• We call the maxPathSumHelper() function on the root node, which calculates the maximum path sum rooted at each node and updates the maxValue accordingly.

• Finally, we return the maxValue, which represents the maximum path sum of the binary tree.

This algorithm has a time complexity of O(n), where n is the number of nodes in the binary tree, as we have to visit each node exactly once.

5. Balanced Binary Tree (LeetCode #110)

1. Problem Description: The problem "Balanced Binary Tree" states that given a binary tree, determine if it is height-balanced. A height-balanced binary tree is defined as a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

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

1. Optimized Java Code with Detailed Comments:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }

    private int height(TreeNode node) {
        // Base case: If node is null, it doesn't contribute to the height
        if (node == null) {
            return 0;
        }
        
        // Recursively calculate the height of left and right subtrees
        int leftHeight = height(node.left);
        int rightHeight = height(node.right);
        
        // If any subtree is unbalanced or the difference between heights of left and right subtrees is more than 1, return -1
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        
        // Return the height of the current node as the maximum of left and right subtree heights plus 1
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

1. Detailed Description and Algorithmic Approach: When approaching this problem during an interview, it is important to understand the concept of a balanced binary tree and how to check if a binary tree is balanced.

A binary tree is balanced if the heights of its left and right subtrees differ by at most one, and the left and right subtrees are also balanced. We can determine if a binary tree is balanced or not using a bottom-up approach.

The algorithm can be defined as follows:

• If the current node is null, it doesn't contribute to the height and we return 0.

• Recursively calculate the heights of the left and right subtrees using depth-first search.

• If any subtree is unbalanced (i.e., its height is -1), or the difference between the heights of the left and right subtrees is greater than 1, return -1 to indicate that the tree is unbalanced.

• Otherwise, return the height of the current node, which is the maximum of the heights of the left and right subtrees plus 1.

By checking the height of each node and comparing the heights of the left and right subtrees, we can determine if the binary tree is balanced or not.

During the interview process, it is important to mention the time and space complexity of the solution. The time complexity is O(n), where n is the number of nodes in the binary tree, as we visit each node once. The space complexity is O(h), where h is the height of the tree, as the maximum call stack size is equal to the height of the tree.