> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/tree/987.-vertical-order-traversal-of-a-binary-tree.md).

# 987. Vertical Order Traversal of a Binary Tree

Given a binary tree, return the *vertical order* traversal of its nodes values.

For each node at position `(X, Y)`, its left and right children respectively will be at positions `(X-1, Y-1)` and `(X+1, Y-1)`.

Running a vertical line from `X = -infinity` to `X = +infinity`, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing `Y` coordinates).

If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.

Return an list of non-empty reports in order of `X` coordinate.  Every report will have a list of values of nodes.

**Example 1:**

![](https://assets.leetcode.com/uploads/2019/01/31/1236_example_1.PNG)

```
Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation: 
Without loss of generality, we can assume the root node is at position (0, 0):
Then, the node with value 9 occurs at position (-1, -1);
The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2);
The node with value 20 occurs at position (1, -1);
The node with value 7 occurs at position (2, -2).
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2019/01/31/tree2.png)

```
Input: [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation: 
The node with value 5 and the node with value 6 have the same position according to the given scheme.
However, in the report "[1,5,6]", the node value of 5 comes first since 5 is smaller than 6.
```

**Note:**

1. The tree will have between 1 and `1000` nodes.
2. Each node's value will be between `0` and `1000`.

```cpp
// Level Order BFS
vector<vector<int>> verticalTraversal(TreeNode* root) { // time: O(nlogn); space: O(n)
    vector<vector<int> > res;
    if (!root) return res;
    map<int, vector<pair<int, int> > > mp; // x->vector<pair<y, value> >
    int x = 0, y = 0;
    queue<pair<TreeNode*, pair<int, int> > > q; // pair<TreeNode*, pair<x, y> >
    q.push({root, {x, y} });
    while (!q.empty()) {
        auto t = q.front(); q.pop();
        TreeNode* node = t.first;
        const pair<int, int>& p = t.second;
        mp[p.first].push_back({p.second, node->val});
        if (node->left) q.push({node->left, {p.first - 1, p.second + 1} });
        if (node->right) q.push({node->right, {p.first + 1, p.second + 1} });
    }
    int n = mp.size();
    res.resize(n);
    int idx = 0;
    for (auto& e : mp) {
        auto& tmp_vec = e.second;
        sort(tmp_vec.begin(), tmp_vec.end());
        for (const pair<int, int>& p : tmp_vec) {
            res[idx].push_back(p.second);
        }
        ++idx;
    }
    return res;
}
```

```cpp
// Recursion
void helper(TreeNode* node, int x, int y, unordered_map<int, unordered_map<int, set<int> > >& mp) {
    if (!node) return;
    mp[x][y].insert(node->val);
    helper(node->left, x - 1, y + 1, mp);
    helper(node->right, x + 1, y + 1, mp);
}
vector<vector<int>> verticalTraversal(TreeNode* root) { // time: O(nlogn); space: O(n)
    vector<vector<int> > res;
    unordered_map<int, unordered_map<int, set<int> > > mp;
    helper(root, 0, 0, mp);
    for (int x = -999; x <= 999; ++x) {
        if (!mp.count(x)) continue;
        res.push_back(vector<int>() );
        for (int y = 0; y < 1000; ++y) {
            if (!mp[x].count(y)) continue;
            res.back().insert(res.back().end(), mp[x][y].begin(), mp[x][y].end());
        }
    }
    return res;
}
```

```cpp
// Recursion
void helper(TreeNode* node, int x, int y, map<pair<int, int>, set<int> >& mp, int& min_x, int& max_x) {
    if (!node) return;
    min_x = min(min_x, x);
    max_x = max(max_x, x);
    mp[{y, x}].insert(node->val);
    helper(node->left, x - 1, y + 1, mp, min_x, max_x);
    helper(node->right, x + 1, y + 1, mp, min_x, max_x);
}
vector<vector<int>> verticalTraversal(TreeNode* root) { // time: O(nlogn); space: O(n)
    vector<vector<int> > res;
    if (!root) return res;
    int min_x = numeric_limits<int>::max(), max_x = numeric_limits<int>::min();
    map<pair<int, int>, set<int> > mp; // {y, x} -> {vals}
    helper(root, 0, 0, mp, min_x, max_x);
    res.resize(max_x - min_x + 1);
    for (const auto& e : mp) {
        int x = e.first.second - min_x;
        res[x].insert(end(res[x]), begin(e.second), end(e.second));
    }
    return res;
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/tree/987.-vertical-order-traversal-of-a-binary-tree.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.