# 4ms C++ solution DFS get tree span + BFS assign column index

• Sharing my solution which runs in 4ms.

DFS to get the left-right span of the tree, so we can avoid reconstructing the final results and we can map our column index directly into final result vector index by final_index = column_index + left_node_span.

BFS to assign column index to each node and add value directly into the result vector.

``````class Solution {
public:
typedef pair<TreeNode*, int> Node;
vector<vector<int>> verticalOrder(TreeNode* root) {
if (root == NULL) return {};

int lc = 0, rc = 0;
getSpan(root, 0, lc, rc);
lc = abs(lc);
int count = lc + rc + 1;

vector<vector<int>> vertical(count);

queue<Node> next;
next.push(Node(root, 0));

while (!next.empty()) {
Node curr = next.front();
next.pop();

TreeNode* node = curr.first;
int idx = curr.second + lc;
vertical[idx].push_back(curr.first->val);

if (node->left) next.push(Node(node->left, curr.second-1));
if (node->right) next.push(Node(node->right, curr.second+1));
}

return vertical;
}

void getSpan(TreeNode* curr, int coord, int& lc, int& rc) {
if (coord < 0) lc = min(lc, coord);
if (coord > 0) rc = max(rc, coord);
if (curr->left) getSpan(curr->left, coord-1, lc, rc);
if (curr->right) getSpan(curr->right, coord+1, lc, rc);
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.