Traversal

1. Preorder Traversal (LeetCode #144)

1. Problem Description: The Preorder Traversal problem on LeetCode, numbered as #144, asks us to return the preorder traversal of a binary tree. Preorder traversal means visiting the root node first, then traversing the left subtree, and finally traversing the right subtree.

LeetCode link: https://leetcode.com/problems/binary-tree-preorder-traversal/

1. Optimized Java Code for Preorder Traversal (LeetCode #144) 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 List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode current = stack.pop();
            result.add(current.val);
            
            // We push right child first so that the left child gets processed first, following the preorder traversal.
            if (current.right != null) {
                stack.push(current.right);
            }
            
            if (current.left != null) {
                stack.push(current.left);
            }
        }
        
        return result;
    }
}

1. Detailed Description of Algorithm and Approach:

During an interview, when presented with this problem, here is how you can think through it:

• Understanding Preorder Traversal: Preorder traversal is a type of tree traversal where we visit the root node first, followed by the left subtree, and then the right subtree.

• Approach:

  • We will use a Stack and a List to solve this problem.

  • Initialize an empty stack and an empty list to store the result.

  • If the root is null, return the empty list.

  • Push the root node onto the stack.

  • While the stack is not empty:

    • Pop the top element from the stack and add its value to the result list.

    • If the node has a right child, push it onto the stack.

    • If the node has a left child, push it onto the stack.

  • After the loop finishes, return the result list.

• Algorithm Explanation:

  • The algorithm starts by checking if the root is null. If it is, we return an empty list since there is no tree to traverse.

  • If the root is not null, we create an empty Stack to store the nodes we need to process.

  • We push the root node into the stack.

  • We enter a while loop that continues until the stack is empty.

  • Inside the while loop, we pop the top node from the stack.

  • We add the value of the popped node to the result list since this is the preorder traversal.

  • We check if the popped node has a right child. If it does, we push it onto the stack.

  • We check if the popped node has a left child. If it does, we push it onto the stack.

  • This order ensures that the left subtree is processed before the right subtree, as required by the preorder traversal.

  • After the while loop finishes, we have processed all nodes in the tree, and the result list contains the preorder traversal.

  • We return the result list as the final answer.

• Complexity Analysis:

  • Time Complexity: O(N), where N is the number of nodes in the tree. We traverse each node exactly once.

  • Space Complexity: O(N), since in the worst case, the stack can store all nodes of the tree.

I hope this explanation helps you understand the problem and its solution approach!

2. Inorder Traversal (LeetCode #94)

1. Problem Description and Link:

The problem "Inorder Traversal" is a classic tree traversal problem on LeetCode. The problem link is: https://leetcode.com/problems/binary-tree-inorder-traversal/

Given the root of a binary tree, return the inorder traversal of its nodes' values. In inorder traversal, we traverse the left subtree, then visit the root, and finally traverse the right subtree.

1. Java Code for Inorder Traversal (with comments):

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorder(root, result); // call helper method to perform inorder traversal
        return result;
    }
    
    private void inorder(TreeNode node, List<Integer> result) {
        if (node == null) {
            return; // base case: empty tree or leaf node reached
        }
        
        inorder(node.left, result); // traverse left subtree
        
        result.add(node.val); // visit current root node
        
        inorder(node.right, result); // traverse right subtree
    }
}

import java.util.ArrayList; import java.util.List; import java.util.Stack;

public class BinaryTreeInorderTraversal {

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null)
        return result;

    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;

    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }

        current = stack.pop();
        result.add(current.val);
        current = current.right;
    }

    return result;
}

public static void main(String[] args) {
    BinaryTreeInorderTraversal solution = new BinaryTreeInorderTraversal();

    // Example usage:
    // Create a binary tree:
    //      1
    //       \
    //        2
    //       /
    //      3
    TreeNode root = new TreeNode(1);
    root.right = new TreeNode(2);
    root.right.left = new TreeNode(3);

    List<Integer> inorder = solution.inorderTraversal(root);
    System.out.println("Inorder Traversal: " + inorder);
}

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

    TreeNode(int x) {
        val = x;
    }
}

}

1. Algorithm and Approach:

The algorithm used to solve this problem is a recursive approach known as "Inorder Traversal". It follows the below steps:

• The base case is when the current node is null, indicating either an empty tree or a leaf node. In this case, we simply return.

• Otherwise, we recursively call the inorder method on the left subtree, to traverse it in an inorder manner.

• After traversing the left subtree and returning, we add the value of the current root node to the result list.

• Lastly, we recursively call the inorder method on the right subtree, to traverse it in an inorder manner.

During an interview process, it is important to understand and explain this algorithm clearly. Here are some guidelines:

• Start by explaining the concept of inorder traversal: left subtree, root, right subtree.

• Discuss the base case for an empty tree or when a leaf node is reached.

• Emphasize the recursive nature of the algorithm.

• Explain how the algorithm processes the left subtree first, then visits the root, and finally processes the right subtree.

• Discuss the space and time complexity of the algorithm: O(n) space, where n is the number of nodes in the tree, as we use additional space for the result list. The time complexity is O(n) as well, as we visit each node exactly once.

3. Postorder Traversal (LeetCode #145)

1. The problem is to perform a postorder traversal on a binary tree. The goal is to visit all nodes in the following order: left child, right child, and then the root. The problem can be found on LeetCode at: https://leetcode.com/problems/binary-tree-postorder-traversal/

2. Java code for the problem "Postorder Traversal (LeetCode #145)":

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

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode current = stack.pop();
            result.add(0, current.val);
            
            if (current.left != null) {
                stack.push(current.left);
            }
            
            if (current.right != null) {
                stack.push(current.right);
            }
        }
        
        return result;
    }
}

1. Detailed description and algorithm:

• The problem requires us to perform a postorder traversal on a binary tree.

• In a postorder traversal, we first visit the left child, then the right child, and finally the root.

• One way to solve this problem is by using a stack and adding nodes to the stack in a specific order.

• We start by initializing an empty stack and pushing the root node to the stack.

• Then, while the stack is not empty, we pop a node from the stack and add its value to the result list at the beginning.

• We push the left child of the current node to the stack if it exists.

• We push the right child of the current node to the stack if it exists.

• This way, when we pop nodes from the stack, the order of nodes being processed is right child, left child, and finally the root, achieving a postorder traversal.

• Finally, we return the result list containing the postorder traversal of the binary tree.

During an interview process, it is important to understand the problem requirements and constraints. Make sure to ask clarifying questions if needed. Discuss the possible approaches and their time and space complexities. Write clean and optimized code with proper comments. Test the code with different inputs to ensure its correctness.

4. Level Order Traversal (LeetCode #102)

1. Problem Description (Level Order Traversal - LeetCode #102): You are given a binary tree. Write a function to return the level order traversal of its nodes' values (from left to right, level by level).

Example: Input: Binary tree [3,9,20,null,null,15,7] 3 / 9 20 / 15 7 Output: [[3],[9,20],[15,7]]

Problem Link: https://leetcode.com/problems/binary-tree-level-order-traversal/

1. Java Code for Level Order Traversal:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

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

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> levelValues = new ArrayList<>();
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                levelValues.add(node.val);
                
                if (node.left != null) {
                    queue.offer(node.left);
                }
                
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            
            result.add(levelValues);
        }
        
        return result;
    }
}

1. Algorithm and Interview Approach:

The problem requires traversing a binary tree level by level and returning the values of nodes at each level in a separate list. This can be solved efficiently using the Breadth-first Search (BFS) algorithm.

1. First, we initialize an empty result list to store the level order traversal.

2. Next, we check if the given tree is empty. If it is, we return the empty result list.

3. We use a queue to perform the BFS traversal. We start by enqueuing the root node.

4. We enter a while loop that continues until the queue is empty.

5. Inside the loop, we determine the number of nodes at the current level by storing the queue size.

6. We create a new levelValues list to store the node values at the current level.

7. We iterate through the nodes in the queue for the current level and add their values to the levelValues list.

8. For each node, if it has a left child, we enqueue it. Similarly, if it has a right child, we enqueue it.

9. Once we finish processing all nodes at the current level, we add the levelValues list to the result.

10. Finally, we return the result list containing the level order traversal.

During an interview, you can explain the algorithm step by step. Emphasize the use of the queue data structure to perform BFS and the iterative approach taken to solve the problem efficiently. Discuss the time and space complexity of the algorithm, which is O(N), where N is the number of nodes in the binary tree.

5. Zigzag Level Order Traversal (LeetCode #103)

1. Problem Description:

The problem "Zigzag Level Order Traversal" asks us to perform a level order traversal on a binary tree and return the nodes' values in a zigzag pattern, i.e., alternating left-to-right and right-to-left.

LeetCode Problem Link: https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

1. Optimal Java Code for "Zigzag Level Order Traversal":

import java.util.*;

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

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

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean isReverse = false;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (isReverse) {
                    level.add(0, node.val); // add to the beginning for reverse order
                } else {
                    level.add(node.val); // add to the end for normal order
                }
                
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            
            result.add(level);
            isReverse = !isReverse; // toggle the zigzag order for each level
        }
        
        return result;
    }
}

1. Algorithm Explanation and Thinking Process:

During an interview, the interviewer might expect you to go through the thinking process and explain the algorithm step-by-step. Here's an explanation for the "Zigzag Level Order Traversal" algorithm:

• The problem requires us to traverse a binary tree level by level and group the nodes' values in zigzag order, i.e., alternate direction.

• To solve this problem, we can use the Breadth-First Search (BFS) approach with a queue.

• We start with an empty result list to store the level order traversal.

• If the root is null, we return the empty result list.

• We create an empty queue and add the root node to it.

• We also create a boolean variable, isReverse, to keep track of whether the current level should be reversed or not.

• While the queue is not empty, we perform the following steps:

  • Get the current size of the queue to know the number of nodes at the current level.

  • Create an empty list, level, to store the values of nodes at the current level.

  • Iterate i from 0 to the current size of the queue:

    • Pop the front node from the queue.

    • If isReverse is true, add the node's value to the beginning of the level list; otherwise, add it to the end.

    • If the node has a left child, enqueue it.

    • If the node has a right child, enqueue it.

  • Add the level list to the result list.

  • Toggle isReverse to its opposite value for the next level.

• Finally, return the result list containing the zigzag level order traversal of the binary tree.

This solution has a time complexity of O(n), where n is the number of nodes in the binary tree, as we visit each node exactly once. The space complexity is O(m), where m is the maximum number of nodes at any level in the tree, as the queue can hold at most the nodes at a level.

6. Vertical Order Traversal of a Binary Tree (LeetCode #987)

1. The problem "Vertical Order Traversal of a Binary Tree" on LeetCode asks us to return the vertical order traversal of a binary tree. In this problem, each node in the tree has a unique value and it may occur in multiple places in the tree. The vertical order is defined by traversing the tree from left to right and top to bottom, where nodes on the same column are grouped together.

Problem Link: https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/

1. Here is the optimized Java code for the problem "Vertical Order Traversal of a Binary Tree" with detailed comments:

import java.util.*;

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

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

class Solution {
    // Custom class to store the node's value and its column number
    class NodeWithColumn {
        TreeNode node;
        int column;

        NodeWithColumn(TreeNode node, int column) {
            this.node = node;
            this.column = column;
        }
    }

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> verticalOrder = new ArrayList<>();
        if (root == null) {
            return verticalOrder;
        }

        // Map to store nodes for each column number
        Map<Integer, List<Integer>> columnNodes = new TreeMap<>();

        // Queue to perform level order traversal of the tree
        Queue<NodeWithColumn> queue = new LinkedList<>();
        queue.offer(new NodeWithColumn(root, 0));

        // Level order traversal
        while (!queue.isEmpty()) {
            int size = queue.size();
            Map<Integer, List<Integer>> levelNodes = new TreeMap<>();

            for (int i = 0; i < size; i++) {
                NodeWithColumn nodeWithColumn = queue.poll();
                TreeNode currNode = nodeWithColumn.node;
                int currColumn = nodeWithColumn.column;

                // Add the current node's value to its column in the map
                levelNodes.computeIfAbsent(currColumn, x -> new ArrayList<>()).add(currNode.val);

                // Process left child
                if (currNode.left != null) {
                    queue.offer(new NodeWithColumn(currNode.left, currColumn - 1));
                }

                // Process right child
                if (currNode.right != null) {
                    queue.offer(new NodeWithColumn(currNode.right, currColumn + 1));
                }
            }

            // Merge level nodes with the general columnNodes map
            for (Map.Entry<Integer, List<Integer>> entry : levelNodes.entrySet()) {
                int column = entry.getKey();
                List<Integer> nodes = entry.getValue();
                columnNodes.computeIfAbsent(column, x -> new ArrayList<>()).addAll(nodes);
            }
        }

        // Convert the values from the columnNodes map to the final result list
        for (List<Integer> nodes : columnNodes.values()) {
            verticalOrder.add(nodes);
        }

        return verticalOrder;
    }
}

1. The algorithm for this problem involves performing a level order traversal of the binary tree and maintaining a map to store the nodes for each column number.

In the solution, we use a custom class NodeWithColumn to store the node's value and its column number. We also use a Map<Integer, List<Integer>> called columnNodes to store the nodes for each column number. We utilize a TreeMap for columnNodes to keep the columns sorted.

We start the level order traversal by enqueueing the root node along with its column number (initially 0) into a queue. Then, in each iteration, we process the nodes at the current level and maintain a separate levelNodes map to store the nodes for the current level. After processing all nodes at the current level, we merge levelNodes with columnNodes to update the nodes for each column.

For each node, we add its value to the corresponding column number in levelNodes. We also enqueue its left and right child (if they exist) by adjusting their column numbers accordingly.

Finally, we iterate through the values in columnNodes and add them to the verticalOrder list.

During an interview, it is important to understand the problem statement clearly and clarify any doubts with the interviewer. It is also essential to approach the problem using an efficient algorithm and optimize the code as much as possible. Testing the code with different test cases and discussing the time and space complexity is also crucial.