[Java/C++] Very simple dfs solution


  • 31

    We know that a binary tree can be represented by an array (assume the root begins from the position with index 1 in the array). If the index of a node is i, the indices of its two children are 2*i and 2*i + 1. The idea is to use two arrays (start[] and end[]) to record the the indices of the leftmost node and rightmost node in each level, respectively. For each level of the tree, the width is end[level] - start[level] + 1. Then, we just need to find the maximum width.

    Java version:

        public int widthOfBinaryTree(TreeNode root) {
            return dfs(root, 0, 1, new ArrayList<Integer>(), new ArrayList<Integer>());
        }
        
        public int dfs(TreeNode root, int level, int order, List<Integer> start, List<Integer> end){
            if(root == null)return 0;
            if(start.size() == level){
                start.add(order); end.add(order);
            }
            else end.set(level, order);
            int cur = end.get(level) - start.get(level) + 1;
            int left = dfs(root.left, level + 1, 2*order, start, end);
            int right = dfs(root.right, level + 1, 2*order + 1, start, end);
            return Math.max(cur, Math.max(left, right));
        }
    

    C++ version (use vector<pair<int,int>> to replace the arrays start and end in Java ):

       int widthOfBinaryTree(TreeNode* root) {
            return dfs(root, 0, 1, vector<pair<int, int>>() = {});
        }
        
        int dfs(TreeNode* root, int level, int order, vector<pair<int, int>>& vec){
            if(root == NULL)return 0;
            if(vec.size() == level)vec.push_back({order, order});
            else vec[level].second = order;
            return max({vec[level].second - vec[level].first + 1, dfs(root->left, level + 1, 2*order, vec), dfs(root->right, level + 1, 2*order + 1, vec)});
        }
    

  • 0

    Hope your advice!


  • 0

    @Hao-Cai said in [Java/C++] Very simple dfs solution:

    We can use an array to represent a BST

    As per my understanding, the question does not say anywhere that the input is a BST - it just calls it a binary tree. I am not sure if it is implicit somewhere that it is a BST.

    (the node root begins from the index 1 in the array)

    Again, this is not mentioned in the question. So, did you come up with this conclusion after looking at the examples (as the root node is 1 in all of them)?

    Thank you.


  • 0

    @BatCoder thanks for your remindance! I used a wrong concept. When I say BST, it means ''the tree''...


  • 0

    @Hao-Cai Thank you. Also, could you please answer my 2nd point as well, about the root node starting at 1? I am not sure where the input tree comes into picture. I am confused because I don't know where we take the nodes values into picture. We are just creating a tree starting with root 1. Where do we take the input into picture?


  • 0

    @BatCoder I think this webpage can answer your 2nd question very well: http://opendatastructures.org/versions/edition-0.1d/ods-java/node52.html.


  • 7

    Great idea, thanks

        private int max = 1;
        public int widthOfBinaryTree(TreeNode root) {
            if (root == null) return 0;
            List<Integer> startOfLevel = new LinkedList<>();
            helper(root, 0, 1, startOfLevel);
            return max;
        }
        public void helper(TreeNode root, int level, int index, List<Integer> list) {
            if (root == null) return;
            if (level == list.size()) list.add(index);
            max = Math.max(max, index + 1 - list.get(level));
            helper(root.left, level + 1, index * 2, list);
            helper(root.right, level + 1, index * 2 + 1, list);
        }
    

  • 0
    J

    @Hao-Cai said in [Java/C++] Very simple dfs solution:

        if(start.size() == level){
            start.add(order); end.add(order);
        }
        else end.set(level, order);
    

    @Hao-Cai could you give some explanation on
    ''' if(start.size() == level){
    start.add(order); end.add(order);
    }
    else end.set(level, order);
    '''
    ? Thanks in advance!


  • 3

    @jyu332 start.size() == level means the traversal arrives a new level of the tree, we need to extend the size of array start and end to put the start index and the end index of this new level into them, respectively. If start.size() != level, it means the traversal is in a visited level, then we just need to update the end index of this level. Note that the dfs in this code is actually a preorder traversal, therefore, when the traversal is in a visited level, the visiting node must be the rightmost node in this level. Hope the explanation can help you!


  • 1
    J

    if you have a very deep tree, would this approach cause integer overflow? and change it to double still having the issue.


  • 0
    J
    This post is deleted!

  • 0

    @jasonyin There is a note in the question: "Answer will in the range of 32-bit signed integer."


  • 1
    J

    @Hao-Cai a tree with right node only and very deep. the answer is 1 which is within 32bit range, but index is overflowed.


  • 0

    @jasonyin Yes, it will get overflow error. But I think this case is unusual.


  • 0
    I

    If each node has right child, after 32 levels, your 'order' will be truncated. Answer could still be within signed 32 bits.


  • 0

    @iaming Yes, so you think we should use long int or something?


  • 0
    I

    long does not solve this issue at all.

            int ans = 0, cnt = 1, width = 0, gap = 0;
            if (root == null) return ans;
            Queue<TreeNode> q = new LinkedList<>();
            Queue<Integer> qi = new LinkedList<>();
            q.offer(root);
            qi.offer(0);
            while (!q.isEmpty()) {
                TreeNode n = q.poll();
                int g = qi.poll();
                cnt--;
                if (n.left != null) {
                    if (cnt < q.size()) qi.offer(gap);
                    q.offer(n.left);
                    gap = 0;
                } else {
                    gap++;
                }
                if (n.right != null) {
                    if (cnt < q.size()) qi.offer(gap);
                    q.offer(n.right);
                    gap = 0;
                } else {
                    gap++;
                }
                width += 1 + g;
                gap += g * 2;
                if (cnt == 0) {
                    cnt = q.size();
                    if (cnt > 0) qi.offer(0);
                    ans = Math.max(ans, width);
                    width = 0;
                }
            }
            return ans;
    

  • 0

    @iaming Since the return value of the given function is int type, I think the result should be a 32-bit signed integer.


  • 0
    S

    @Hao-Cai said in [Java/C++] Very simple dfs solution:

    level

    Can you explain the what is "order" here in your helper method "dfs"?


  • 1

    @Shayy It's the index if you write the tree as an array.


Log in to reply
 

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