C++, O(N), DFS/preorder traversal


  • 7
    Z

    We can easily get the dimensions of the ans, which is height and width of the tree, by DFS. The remaining work is to recursively preorder or other traversal of the tree.

    Note a big number "1234567" takes the same space as "1". I misunderstood the question and came into a bit more complex problem.

    Except initializing the answer of m row and n column, the run time is O(N). Here m is the height of the tree, n = 2^m-1, and N is how many nodes of the tree. In the worst case, for example, a tree with only left child, we have m = N, so the initialization is O(N x 2^N). Fortunately, m <= 10, so initialization is O(10000). When m is a big number, this can be an issue and we will have memory error as well.

    Here I assume initialization using empty string is very fast. I did a test by adding the code below to show initialization is not the limiting factor.

    vector<vector<string>> ans;
    int k = 1000;
    for (int i = 0; i < k; i++)
           ans = vector<vector<string>>(h, vector<string>(w, ""));
    

    k = 1, 3 ms;
    k = 10, 3 ms;
    k = 100, 9-12 ms;
    k = 1000, ~70 ms;
    So initialization seems huge, but only takes about 6-7% of total run time.

    class Solution {
    public:
        vector<vector<string>> printTree(TreeNode* root) {
            int h = get_height(root), w = get_width(root);
            vector<vector<string>> ans(h, vector<string>(w, ""));
            helper(ans, root, 0, 0, w-1);
            return ans;
        }
    private:
        int get_height(TreeNode* p) {
            if (!p) return 0;
            int left = get_height(p->left), right = get_height(p->right);
            return max(left, right)+1;
        }
        // width is the max(left, right)*2+1
        int get_width(TreeNode* p) {
            if (!p) return 0;
            int left = get_width(p->left), right = get_width(p->right);
            return max(left, right)*2+1;
        }
        // always put the value in the middle of the range.
        void helper(vector<vector<string>>& ans, TreeNode* p, int level, int l, int r) {
            if (!p) return;
            int mid = l+(r-l)/2;
            ans[level][mid] = to_string(p->val);
            helper(ans, p->left, level+1, l, mid-1);
            helper(ans, p->right, level+1, mid+1, r);
        }
    };
    

  • 0

    How do you think it's O(n)? Do you think m is a constant?


  • 0
    Z

    @ManuelP I totally understand your concern. For an answer of m row and n column, the initialization part will be O(mn). However, I feel it doesn't precisely represent the algorithm run time. In addition, m <= 10, and n <= 1100 because the tree height <= 10.


  • 0
    D

    @ManuelP n=2^m-1. I think it's O(nlogn).


  • 0
    Z

    @Dixin It can be O(n x 2^n). I have added more details in the original post.


  • 0

    @zestypanda I came up with a very similar solution, however, I derived the width from the depth, since we are constructing enough space to fit a complete binary tree, we know the width is 2^(depth+1)-1. This allows us to avoid additional inefficient recursive calls. Also, we can check for NULL nodes before invoking the recursive calls for finding the depth and filling in the table with values, since N+1 nodes of a binary tree of size N are NULL. This reduces the amount of recursive calls by half.

    As you've mentioned, the tree size is small, so these optimizations are good practice, but near irrelevant for increasing the time efficiency for solving this problem.

    class Solution{
    public:
        vector<vector<string>> printTree(TreeNode* root){
            
            vector<vector<string>> res;
            
            //
            // create table of empty strings ""
            // based on the tree height/width
            //
            int depth = maxDepth(root);
            int width = pow(2, depth+1) - 1;
            vector<string> row (width, "");
            for (int i=0; i <= depth; i++){
                res.push_back(row);
            }
            
            //
            // traverse the tree and fill in table values for non-NULL nodes
            //
            fillTable(root, 0, 0, width-1, res);
            return res;
        }
        
    private:
        int maxDepth(TreeNode* node){
            if (!node) { return -1; }
            
            int leftDepth = -1;
            if (node->left) { leftDepth = maxDepth(node->left); }
            
            int rightDepth = -1;
            if (node->right) { rightDepth = maxDepth(node->right); }
            
            return 1 + max( leftDepth, rightDepth );
        }
        
        void fillTable(TreeNode* node, int depth, int start, int end, vector<vector<string>>& table){
            if (!node) { return; }
            
            int mid = (int)(start+end)/2;
            table[depth][mid] = to_string(node->val);
            
            if (node->left)  { fillTable(node->left,  depth+1, start, mid-1, table); }
            if (node->right) { fillTable(node->right, depth+1, mid+1, end,   table); }
        }
    };
    

Log in to reply
 

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