[C++/Java] * [BFS/DFS/3liner] Clean Code With Explanation


  • 19

    The idea is to use heap indexing:

            1
       2         3
     4   5     6   7
    8 9 x 11  x 13 x 15
    

    Regardless whether these nodes exist:

    • Always make the id of left child as parent_id * 2;
    • Always make the id of right child as parent_id * 2 + 1;

    So we can just:

    1. Record the id of left most node when first time at each level of the tree during an pre-order run.(you can tell by check the size of the container to hold the first nodes);
    2. At each node, compare the distance from it the left most node with the current max width;

    DFS - Return Value
    C++

    class Solution {
    public:
        int widthOfBinaryTree(TreeNode* root) {
            vector<int> lefts; // left most nodes at each level;
            return dfs(root, 1, 0, lefts);
        }
    private:
        int dfs(TreeNode* n, int id, int d, vector<int>& lefts) { // d : depth
            if (!n) return 0;
            if (d >= lefts.size()) lefts.push_back(id);  // add left most node
            return max({id + 1 - lefts[d], dfs(n->left, id * 2, d + 1, lefts), dfs(n->right, id * 2 + 1, d + 1, lefts)});
        }
    };
    

    3 liner

    class Solution {
    public:
        int widthOfBinaryTree(TreeNode* root) {
            unordered_map<int, vector<int>> m;
            function<int(TreeNode*, int, int)> dfs = [&](TreeNode* n, int id, int d){ return n ? m[d].push_back(id), max({id+1-m[d][0], dfs(n->left, id*2, d+1), dfs(n->right, id*2+1, d+1)}) : 0; };
            return dfs(root, 1, 0);
        }
    };
    

    Java

    class Solution {
        public int widthOfBinaryTree(TreeNode root) {
            List<Integer> lefts = new ArrayList<Integer>(); // left most nodes at each level;
            return dfs(root, 1, 0, lefts);
        }
    
        private int dfs(TreeNode n, int id, int d, List<Integer> lefts) { // d : depth
            if (n == null) return 0;
            if (d >= lefts.size()) lefts.add(id);   // add left most node
            return Math.max(id + 1 - lefts.get(d), Math.max(dfs(n.left, id*2, d+1, lefts), dfs(n.right, id*2+1, d+1, lefts)));
        }
    }
    

    DFS - Side Effect
    C++

    class Solution {
    public:
        int widthOfBinaryTree(TreeNode* root) {
            vector<int> lefts; // left most nodes at each level;
            int maxwidth = 0;
            dfs(root, 1, 0, lefts, maxwidth);
            return maxwidth;
        }
    private:
        void dfs(TreeNode* node, int id, int depth, vector<int>& lefts, int& maxwidth) {
            if (!node) return;
            if (depth >= lefts.size()) lefts.push_back(id);  // add left most node
            maxwidth = max(maxwidth, id + 1 - lefts[depth]);
            dfs(node->left, id * 2, depth + 1, lefts, maxwidth);
            dfs(node->right, id * 2 + 1, depth + 1, lefts, maxwidth);
        }
    };
    

    Java

    class Solution {
        public int widthOfBinaryTree(TreeNode root) {
            List<Integer> lefts = new ArrayList<Integer>(); // left most nodes at each level;
            int[] res = new int[1]; // max width
            dfs(root, 1, 0, lefts, res);
            return res[0];
        }
        private void dfs(TreeNode node, int id, int depth, List<Integer> lefts, int[] res) {
            if (node == null) return;
            if (depth >= lefts.size()) lefts.add(id);   // add left most node
            res[0] = Integer.max(res[0], id + 1 - lefts.get(depth));
            dfs(node.left,  id * 2,     depth + 1, lefts, res);
            dfs(node.right, id * 2 + 1, depth + 1, lefts, res);
        }
    }
    

    BFS
    C++

    class Solution {
    public:
        int widthOfBinaryTree(TreeNode* root) {
            if (!root) return 0;
            int max = 0;
            queue<pair<TreeNode*, int>> q;
            q.push(pair<TreeNode*, int>(root, 1));
            while (!q.empty()) {
                int l = q.front().second, r = l; // right started same as left
                for (int i = 0, n = q.size(); i < n; i++) {
                    TreeNode* node = q.front().first;
                    r = q.front().second;
                    q.pop();
                    if (node->left) q.push(pair<TreeNode*, int>(node->left, r * 2));
                    if (node->right) q.push(pair<TreeNode*, int>(node->right, r * 2 + 1));
                }
                max = std::max(max, r + 1 - l);
            }
            return max;
        }
    };
    

    Java

    import java.util.AbstractMap;
    class Solution {
        public int widthOfBinaryTree(TreeNode root) {
            if (root == null) return 0;
            int max = 0;
            Queue<Map.Entry<TreeNode, Integer>> q = new LinkedList<Map.Entry<TreeNode, Integer>>();
            q.offer(new AbstractMap.SimpleEntry(root, 1));
    
            while (!q.isEmpty()) {
                int l = q.peek().getValue(), r = l; // right started same as left
                for (int i = 0, n = q.size(); i < n; i++) {
                    TreeNode node = q.peek().getKey();
                    r = q.poll().getValue();
                    if (node.left != null) q.offer(new AbstractMap.SimpleEntry(node.left, r * 2));
                    if (node.right != null) q.offer(new AbstractMap.SimpleEntry(node.right, r * 2 + 1));
                }
                max = Math.max(max, r + 1 - l);
            }
    
            return maxwidth;
        }
    }
    

  • 0

    @alexander Thank you for your answer. I had a quick question. As per my understanding, the question does not mention that the tree is always rooted at 1. During the contest, what made you think that it will always be rooted at 1 (and consequently think about the above approach)?


  • 0
    C

    @BatCoder
    Because zero does not work : 2*0 == 0 which means left child will override parent. As he has pointed out briefly, this array indexing is generally been seen in priority queue, e.g. max/min heap which is used for example in heap-sort. See here for example: http://www.always-a-programmer.com/blog/sort/#section-heap-sort


  • 0

    Is it faster to use an array to record the current maximum width?


  • 0

    @captainjtx Sorry, let me rephrase my question. Why isn't it assumed that the root node can start at number, like say, 5? The value of id has been hard-coded by @alexander to be 1; what is the intuition behind starting with 1 and not something like 5?


  • 0
    C

    @BatCoder
    Okay, if you use other number n other than 1. The left child of root would be 2n-1 and right child would be 2n+1. The width of the second depth would be (2n+1-2n-1) = n+1. You can see only n=1 makes sense. Like I said, this indexing is initially seen in the array representation of binary tree, especially max/min heap. You may wanna take a closer look at the binary tree @alexander draw. The numbers he put in the tree can actually be seen as index to a one-based array. It's like this, root is the first element in the array. Left child is the second element right child is the third element and so on. For a complete binary tree, it is not difficult to prove that for any node, it is left child can be indexed as 2n-1 and right child can be indexed as 2n+1. Hope you find it useful


  • 0
    J
    This post is deleted!

  • 1
    A

    There is a test case where tree only has right nodes. In that case the index of the node will overflow.
    Luckily, that case is passed in this code. I think there is a testcase possible for which this code might fail.


  • 0

    @arjunjajoo In that case, you can submit a testcase so that the admin would add it. In order to do this, you need to hit the Contribute button near the text box wherein the test cases are displayed (below the editor). Thanks!


  • 1

    Give each binary tree node a index, just like heap:

              root: i
    left:i * 2   right: i * 2 + 1
    

    List<Integer> lefts records the left-most index of one level.
    Compare all nodes distance to its level left-most node.

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

Log in to reply
 

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