How to Find the Vertical Order Traversal of a Binary Tree using DFS Algorithm?

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). The tree will have between 1 and 1000 nodes. Each node’s value will be between 0 and 1000.

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:
Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

Explanation:

vertical-binary-tree-order-1

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:
Input: [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]

vertical-binary-tree-order-2

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.

Storing the locations of nodes using Depth First Search Algorithm

We define the root location coordinate as (0, 0). If we go left node, we decrement the X coordinate and if we go to the right node, we increment the X coordinate. In both cases, the Y coordinate is increment as it goes to the next level.

We use the Depth First Search (DFS) algorithm to traverse all the nodes in the binary tree, then we sort all the nodes by the coordinates (from the left to right, and from the up to the down, if two nodes having the same location, the smaller value comes first).

Then, we group the sorted nodes by X coordinate.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        vector<tuple<int, int, int>> res;
        dfs(root, res, 0, 0); // store the coordinates of nodes
        sort(begin(res), end(res), [](auto a, auto b) {
            int x1 = std::get<0>(a);
            int y1 = std::get<1>(a);
            int v1 = std::get<2>(a);
            int x2 = std::get<0>(b);
            int y2 = std::get<1>(b);
            int v2 = std::get<2>(b);
            if (x1 < x2) return true;
            if ((x1 == x2) && (y1 == y2)) return v1 < v2;
            if (x1 == x2) return y1 < y2;
            return false;
        });
        int level = INT_MIN;
        vector<int> cur;
        vector<vector<int>> r;
        for (const auto &n: res) {
            int x = std::get<0>(n);
            int y = std::get<1>(n);
            int z = std::get<2>(n);
            if ((level == INT_MIN) || (x == level)) {
                cur.push_back(z);
            } else {
                r.push_back(cur);
                cur = {z};
            }
            level = x;
        }
        r.push_back(cur);
        return r;
    }
    
private:
    void dfs(TreeNode* root, vector<tuple<int, int, int>> &res, int x, int y) {
        if (root == nullptr) return;
        res.push_back(make_tuple(x, y, root->val));
        dfs(root->left, res, x - 1, y + 1);
        dfs(root->right, res, x + 1, y + 1);
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        vector<tuple<int, int, int>> res;
        dfs(root, res, 0, 0); // store the coordinates of nodes
        sort(begin(res), end(res), [](auto a, auto b) {
            int x1 = std::get<0>(a);
            int y1 = std::get<1>(a);
            int v1 = std::get<2>(a);
            int x2 = std::get<0>(b);
            int y2 = std::get<1>(b);
            int v2 = std::get<2>(b);
            if (x1 < x2) return true;
            if ((x1 == x2) && (y1 == y2)) return v1 < v2;
            if (x1 == x2) return y1 < y2;
            return false;
        });
        int level = INT_MIN;
        vector<int> cur;
        vector<vector<int>> r;
        for (const auto &n: res) {
            int x = std::get<0>(n);
            int y = std::get<1>(n);
            int z = std::get<2>(n);
            if ((level == INT_MIN) || (x == level)) {
                cur.push_back(z);
            } else {
                r.push_back(cur);
                cur = {z};
            }
            level = x;
        }
        r.push_back(cur);
        return r;
    }
    
private:
    void dfs(TreeNode* root, vector<tuple<int, int, int>> &res, int x, int y) {
        if (root == nullptr) return;
        res.push_back(make_tuple(x, y, root->val));
        dfs(root->left, res, x - 1, y + 1);
        dfs(root->right, res, x + 1, y + 1);
    }
};

The above C++ uses the tuple to store X-Y coordinate and the value. The overall time complexity is dominated by the sorting which takes O(nlogn). The space complexity is O(H + N) where H is the height of the tree, thus O(N).

Actually, we don’t need to write the custom comparator. As the default comparator in C++ is to compare the first dimension, then second dimension and so on. Thus, the following:

sort(begin(res), end(res), [](auto a, auto b) {
   int x1 = std::get<0>(a);
   int y1 = std::get<1>(a);
   int v1 = std::get<2>(a);
   int x2 = std::get<0>(b);
   int y2 = std::get<1>(b);
   int v2 = std::get<2>(b);
   if (x1 < x2) return true;
   if ((x1 == x2) && (y1 == y2)) return v1 < v2;
   if (x1 == x2) return y1 < y2;
   return false;
});

sort(begin(res), end(res), [](auto a, auto b) {
   int x1 = std::get<0>(a);
   int y1 = std::get<1>(a);
   int v1 = std::get<2>(a);
   int x2 = std::get<0>(b);
   int y2 = std::get<1>(b);
   int v2 = std::get<2>(b);
   if (x1 < x2) return true;
   if ((x1 == x2) && (y1 == y2)) return v1 < v2;
   if (x1 == x2) return y1 < y2;
   return false;
});

can just be replaced by the following:

1	sort(begin(res), end(res));

sort(begin(res), end(res));

Update: a year later, I reimplement this, and surprised to have a slightly different implementation:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        vector<vector<int>> nodes;
        dfs(nodes, root, 0, 0);
        map<int, vector<vector<int>>> data;
        for (const auto &n: nodes) {
            data[n[0]].push_back({n[1], n[2]});
        }
        vector<vector<int>> ans;
        for (auto it = begin(data); it != end(data); ++ it) {
            auto cur = it->second;
            sort(begin(cur), end(cur));
            vector<int> arr;
            for (const auto &n: cur) {
                arr.push_back(n[1]);
            }
            ans.push_back(arr);
        }
        return ans;
    }
    
private:
    void dfs(vector<vector<int>> &nodes, TreeNode* root, int x, int y) {
        if (!root) return;
        nodes.push_back({x, y, root->val});
        if (root->left) {
            dfs(nodes, root->left, x - 1, y + 1);
        } 
        if (root->right) {
            dfs(nodes, root->right, x + 1, y + 1);
        }
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        vector<vector<int>> nodes;
        dfs(nodes, root, 0, 0);
        map<int, vector<vector<int>>> data;
        for (const auto &n: nodes) {
            data[n[0]].push_back({n[1], n[2]});
        }
        vector<vector<int>> ans;
        for (auto it = begin(data); it != end(data); ++ it) {
            auto cur = it->second;
            sort(begin(cur), end(cur));
            vector<int> arr;
            for (const auto &n: cur) {
                arr.push_back(n[1]);
            }
            ans.push_back(arr);
        }
        return ans;
    }
    
private:
    void dfs(vector<vector<int>> &nodes, TreeNode* root, int x, int y) {
        if (!root) return;
        nodes.push_back({x, y, root->val});
        if (root->left) {
            dfs(nodes, root->left, x - 1, y + 1);
        } 
        if (root->right) {
            dfs(nodes, root->right, x + 1, y + 1);
        }
    }
};

In this version, we use a map (which keeps the keys sorted, thus in this case, representing the ascending X), then we need to sort the elements by Y order, then value.

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...

1154 words
Last Post: Using BackTracking Algorithm to Find the Combination Integer Sum
Next Post: Algorithm to Decode Run-Length Compression String

The Permanent URL is: How to Find the Vertical Order Traversal of a Binary Tree using DFS Algorithm?

Algorithms, Blockchain and Cloud

How to Find the Vertical Order Traversal of a Binary Tree using DFS Algorithm?

Storing the locations of nodes using Depth First Search Algorithm

Leave a Reply

Storing the locations of nodes using Depth First Search Algorithm

Related posts:

Leave a Reply