Untitled

To solve the problem of finding the **vertical traversal** of a binary tree, the goal is to group nodes based on their horizontal distances (HD) from the root, process them level by level (as per level order traversal), and finally print the nodes grouped by their vertical levels, from leftmost to rightmost.

---

### **Approach**
1. **Horizontal Distance (HD):**
   - The horizontal distance of the root is `0`.
   - For the left child of a node, HD = parent’s HD - 1.
   - For the right child of a node, HD = parent’s HD + 1.

2. **Level Order Traversal:**
   - Traverse the tree level by level while maintaining the horizontal distance of each node.
   - Use a queue to process nodes for level order traversal, where each element in the queue is a pair of `(node, HD)`.

3. **Group Nodes by HD:**
   - Use a `TreeMap<Integer, List<Integer>>` to store nodes at each horizontal distance. The `TreeMap` ensures that the keys (HDs) are sorted from leftmost to rightmost.

4. **Extract the Result:**
   - Iterate over the entries in the `TreeMap` and append the values to the result list.

---

### **Algorithm**
1. Initialize a `TreeMap<Integer, List<Integer>>` to group nodes by HD.
2. Use a `Queue<Pair<TreeNode, Integer>>` to perform level order traversal, where each pair contains a node and its HD.
3. For each node, calculate its HD, add it to the `TreeMap`, and enqueue its left and right children (if present) with their respective HDs.
4. Once traversal is complete, extract the grouped nodes from the `TreeMap` and return them.

---

### **Java Implementation**

```java
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;

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

public class VerticalTraversal {

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

        // TreeMap to store nodes grouped by horizontal distance
        TreeMap<Integer, List<Integer>> map = new TreeMap<>();

        // Queue for level order traversal: stores pairs of (node, HD)
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>(root, 0));

        while (!queue.isEmpty()) {
            Pair<TreeNode, Integer> current = queue.poll();
            TreeNode node = current.getKey();
            int hd = current.getValue();

            // Add the node's value to the corresponding HD list
            map.putIfAbsent(hd, new ArrayList<>());
            map.get(hd).add(node.val);

            // Enqueue the left and right children with updated HDs
            if (node.left != null) {
                queue.offer(new Pair<>(node.left, hd - 1));
            }
            if (node.right != null) {
                queue.offer(new Pair<>(node.right, hd + 1));
            }
        }

        // Prepare the result by flattening the TreeMap values
        List<Integer> result = new ArrayList<>();
        for (List<Integer> group : map.values()) {
            result.addAll(group);
        }

        return result;
    }

    public static void main(String[] args) {
        // Example 1
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(2);
        root1.right = new TreeNode(3);
        root1.left.left = new TreeNode(4);
        root1.left.right = new TreeNode(5);
        root1.right.right = new TreeNode(6);
        root1.right.right.left = new TreeNode(8);
        root1.right.right.right = new TreeNode(9);

        VerticalTraversal vt = new VerticalTraversal();
        System.out.println(vt.verticalTraversal(root1)); // Output: [4, 2, 1, 5, 6, 3, 8, 7, 9]

        // Example 2
        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(2);
        root2.right = new TreeNode(3);
        root2.left.left = new TreeNode(4);
        root2.left.right = new TreeNode(5);
        root2.right.right = new TreeNode(6);
        System.out.println(vt.verticalTraversal(root2)); // Output: [4, 2, 1, 5, 3, 6]
    }
}

// Helper class to store a pair of (node, horizontal distance)
class Pair<K, V> {
    private final K key;
    private final V value;

    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }

    public K getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }
}
```

---

### **Explanation of the Example**

#### Example Input:
```
Tree:
       1
    /     \
   2       3
 /   \       \
4     5       6
```

#### Step-by-Step Vertical Traversal:
1. Start with the root node `1` at HD = `0`.
2. Add left child `2` at HD = `-1` and right child `3` at HD = `+1`.
3. Add `4` at HD = `-2`, `5` at HD = `0`, and `6` at HD = `+2`.
4. Group nodes by HD:
   - HD = `-2`: [4]
   - HD = `-1`: [2]
   - HD = `0`: [1, 5]
   - HD = `+1`: [3]
   - HD = `+2`: [6]

#### Output:
\[4, 2, 1, 5, 3, 6\]

---

### **Complexity Analysis**
1. **Time Complexity**:
   - Level order traversal visits each node once: \( O(n) \).
   - Inserting into `TreeMap` takes \( O(\log(k)) \), where \( k \) is the number of unique HDs (at most \( n \)).
   - Total: \( O(n \log(k)) \), and \( k \leq n \), so it simplifies to \( O(n \log(n)) \).

2. **Space Complexity**:
   - Queue for level order traversal: \( O(n) \).
   - `TreeMap` to store nodes: \( O(n) \).
   - Total: \( O(n) \).