662. Maximum Width of Binary Tree

// LeetCode URL: https://leetcode.com/problems/maximum-width-of-binary-tree/
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

/**
 * DFS
 *
 * 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.
 *
 * Time Complexity: O(N)
 *
 * Space Complexoty: O(Hieght of the tree) = O(N) in worst case (Recursion
 * Stack)
 *
 * N = NUmber of nodes in the tree.
 */
class Solution1 {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int[] result = new int[1];
        dfsHelper(root, 0, 1, new HashMap<>(), result);
        return result[0];
    }

    private void dfsHelper(TreeNode node, int depth, int pos, HashMap<Integer, Integer> map, int[] result) {
        if (node == null) {
            return;
        }
        if (!map.containsKey(depth)) {
            map.put(depth, pos);
        }

        result[0] = Math.max(result[0], pos - map.get(depth) + 1);
        dfsHelper(node.left, depth + 1, 2 * pos, map, result);
        dfsHelper(node.right, depth + 1, 2 * pos + 1, map, result);
    }
}

/**
 * BFS
 *
 * Refer above solution for explaination.
 *
 * Time Complexity: O(N)
 *
 * Space Complexoty: O(Hieght of the tree) = O(N) in worst case (Queue size)
 *
 * N = NUmber of nodes in the tree.
 */
class Solution2 {
    class Node {
        TreeNode node;
        int pos;

        Node(TreeNode n, int p) {
            node = n;
            pos = p;
        }
    }

    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(root, 1));
        int result = 0;

        while (!queue.isEmpty()) {
            int queueSize = queue.size();
            Node leftNode = null;
            for (int i = 0; i < queueSize; i++) {
                Node cur = queue.poll();
                if (cur.node.left != null) {
                    queue.offer(new Node(cur.node.left, cur.pos * 2));
                }
                if (cur.node.right != null) {
                    queue.offer(new Node(cur.node.right, cur.pos * 2 + 1));
                }
                if (leftNode == null) {
                    leftNode = cur;
                }

                result = Math.max(result, cur.pos - leftNode.pos + 1);
            }
        }

        return result;
    }
}