This week has gone by so fast; at least it seems so. We have to take into account that Monday was Labor Day so most people, including myself, had the day off. Today is Friday and it is almost lunch time. I am done with a work task, so I decided to get this post done, have lunch and then start the next work task this afternoon.
There is a lot of code, but I generated a candidate for a solution that seemed to work but was too slow to be accepted by LeetCode. Let me elaborate on the specifics.
I decided to write code to determine the maximum width of a binary tree. My approach was to solve it using a breadth first search approach. On every level I would figure out the width and compare and if needed update a maximum. I believe that worked fine. My requirements should read as follows:
Given a binary tree, write a function to get the maximum width of the given tree. Width of a tree is maximum of widths of all levels.
After that was done, I decided to check on HackerRank and LeetCode if they had this requirement (probably in the title) so I could get credit for my solution. Was not able to find a problem in HackerRank but did find something similar, but different and harder, in LeetCode. If interested take a look at problem 662 Maximum Width of Binary Tree. The requirements for the LeetCode follow:
Given a binary tree, write a function to get the maximum width of the given tree. The maximum width of a tree is the maximum width among all levels. The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation. It is guaranteed that the answer will in the range of 32-bit signed integer.
The main difference is how the width of a level is defined. In my case, a level counts the nodes. In the LeetCode problem, the width needs to take into account the null / missing values from a level. That requires a lot more work and a different approach.
I will show all the code that I used to generate the solution to my problem. I will then the code that I generated for the LeetCode solution which timed out so it was not accepted. At that point, I decided to do some research and found a completely different approach that I used to solve it.
1,2,3
main <<< bfsTraversal:
1
2 3
main <<< maxBTWidth: 2
main <<< widthOfBinaryTree1: 2
getWidth <<< depth: 1 position: 0
getWidth <<< depthLeftPosition: {1=0}
getWidth <<< maxWidth: 1
getWidth <<< depth: 2 position: 0
getWidth <<< depthLeftPosition: {1=0, 2=0}
getWidth <<< maxWidth: 1
getWidth <<< depth: 2 position: 1
getWidth <<< depthLeftPosition: {1=0, 2=0}
getWidth <<< maxWidth: 2
main <<< widthOfBinaryTree: 2
main <<< depthLeftPosition: {1=0, 2=0}
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
main <<< bfsTraversal:
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
main <<< maxBTWidth: 8
main <<< widthOfBinaryTree1: 8
getWidth <<< depth: 1 position: 0
getWidth <<< depthLeftPosition: {1=0}
getWidth <<< maxWidth: 1
getWidth <<< depth: 2 position: 0
getWidth <<< depthLeftPosition: {1=0, 2=0}
getWidth <<< maxWidth: 1
getWidth <<< depth: 3 position: 0
getWidth <<< depthLeftPosition: {1=0, 2=0, 3=0}
getWidth <<< maxWidth: 1
getWidth <<< depth: 4 position: 0
getWidth <<< depthLeftPosition: {1=0, 2=0, 3=0, 4=0}
getWidth <<< maxWidth: 1
getWidth <<< depth: 4 position: 1
getWidth <<< depthLeftPosition: {1=0, 2=0, 3=0, 4=0}
getWidth <<< maxWidth: 2
getWidth <<< depth: 3 position: 1
getWidth <<< depthLeftPosition: {1=0, 2=0, 3=0, 4=0}
getWidth <<< maxWidth: 2
getWidth <<< depth: 4 position: 2
getWidth <<< depthLeftPosition: {1=0, 2=0, 3=0, 4=0}
getWidth <<< maxWidth: 3
getWidth <<< depth: 4 position: 3
getWidth <<< depthLeftPosition: {1=0, 2=0, 3=0, 4=0}
getWidth <<< maxWidth: 4
getWidth <<< depth: 2 position: 1
getWidth <<< depthLeftPosition: {1=0, 2=0, 3=0, 4=0}
getWidth <<< maxWidth: 4
getWidth <<< depth: 3 position: 2
getWidth <<< depthLeftPosition: {1=0, 2=0, 3=0, 4=0}
getWidth <<< maxWidth: 4
getWidth <<< depth: 4 position: 4
getWidth <<< depthLeftPosition: {1=0, 2=0, 3=0, 4=0}
getWidth <<< maxWidth: 5
getWidth <<< depth: 4 position: 5
getWidth <<< depthLeftPosition: {1=0, 2=0, 3=0, 4=0}
getWidth <<< maxWidth: 6
getWidth <<< depth: 3 position: 3
getWidth <<< depthLeftPosition: {1=0, 2=0, 3=0, 4=0}
getWidth <<< maxWidth: 6
getWidth <<< depth: 4 position: 6
getWidth <<< depthLeftPosition: {1=0, 2=0, 3=0, 4=0}
getWidth <<< maxWidth: 7
getWidth <<< depth: 4 position: 7
getWidth <<< depthLeftPosition: {1=0, 2=0, 3=0, 4=0}
getWidth <<< maxWidth: 8
main <<< widthOfBinaryTree: 8
main <<< depthLeftPosition: {1=0, 2=0, 3=0, 4=0}
1,3,2,5,3,null,9
main <<< bfsTraversal:
1
3 2
5 3 null 9
main <<< maxBTWidth: 3
main <<< widthOfBinaryTree1: 4
getWidth <<< depth: 1 position: 0
getWidth <<< depthLeftPosition: {1=0}
getWidth <<< maxWidth: 1
getWidth <<< depth: 2 position: 0
getWidth <<< depthLeftPosition: {1=0, 2=0}
getWidth <<< maxWidth: 1
getWidth <<< depth: 3 position: 0
getWidth <<< depthLeftPosition: {1=0, 2=0, 3=0}
getWidth <<< maxWidth: 1
getWidth <<< depth: 3 position: 1
getWidth <<< depthLeftPosition: {1=0, 2=0, 3=0}
getWidth <<< maxWidth: 2
getWidth <<< depth: 2 position: 1
getWidth <<< depthLeftPosition: {1=0, 2=0, 3=0}
getWidth <<< maxWidth: 2
getWidth <<< depth: 3 position: 3
getWidth <<< depthLeftPosition: {1=0, 2=0, 3=0}
getWidth <<< maxWidth: 4
main <<< widthOfBinaryTree: 4
main <<< depthLeftPosition: {1=0, 2=0, 3=0}
1,3,null,5,3
main <<< bfsTraversal:
1
3 null
5 3
main <<< maxBTWidth: 2
main <<< widthOfBinaryTree1: 2
getWidth <<< depth: 1 position: 0
getWidth <<< depthLeftPosition: {1=0}
getWidth <<< maxWidth: 1
getWidth <<< depth: 2 position: 0
getWidth <<< depthLeftPosition: {1=0, 2=0}
getWidth <<< maxWidth: 1
getWidth <<< depth: 3 position: 0
getWidth <<< depthLeftPosition: {1=0, 2=0, 3=0}
getWidth <<< maxWidth: 1
getWidth <<< depth: 3 position: 1
getWidth <<< depthLeftPosition: {1=0, 2=0, 3=0}
getWidth <<< maxWidth: 2
main <<< widthOfBinaryTree: 2
main <<< depthLeftPosition: {1=0, 2=0, 3=0}
1,3,2,5
main <<< bfsTraversal:
1
3 2
5 null null null
main <<< maxBTWidth: 2
main <<< widthOfBinaryTree: 2
1,2,3,4,5,null,8,null,null,null,null,null,null,6,7
main <<< bfsTraversal:
1
2 3
4 5 null 8
null null null null 6 7
main <<< maxBTWidth: 3
main <<< widthOfBinaryTree: 4
1,3,2,5,null,null,9,6,null,null,null,null,null,null,7
main <<< bfsTraversal:
1
3 2
5 null null 9
6 null null 7
main <<< maxBTWidth: 2
main <<< widthOfBinaryTree: 8
1,3,2,5,null,null,9,6,null,null,null,null,null,7,null
main <<< bfsTraversal:
1
3 2
5 null null 9
6 null 7 null
main <<< maxBTWidth: 2
main <<< widthOfBinaryTree: 7
1,3,2,5,null,null,9,null,6,null,null,null,null,null,7
main <<< bfsTraversal:
1
3 2
5 null null 9
null 6 null 7
main <<< maxBTWidth: 2
main <<< widthOfBinaryTree: 7
1,3,2,5,null,null,9,null,6,null,null,null,null,7,null
main <<< bfsTraversal:
1
3 2
5 null null 9
null 6 7 null
main <<< maxBTWidth: 2
main <<< widthOfBinaryTree: 6
1,2,3,null,null,null,4,null,null,null,null,null,null,null,5
main <<< bfsTraversal:
1
2 3
null null null 4
null 5
main <<< maxBTWidth: 2
main <<< widthOfBinaryTree1: 2
getWidth <<< depth: 1 position: 0
getWidth <<< depthLeftPosition: {1=0}
getWidth <<< maxWidth: 1
getWidth <<< depth: 2 position: 0
getWidth <<< depthLeftPosition: {1=0, 2=0}
getWidth <<< maxWidth: 1
getWidth <<< depth: 3 position: 0
getWidth <<< depth: 3 position: 1
getWidth <<< depth: 2 position: 1
getWidth <<< depthLeftPosition: {1=0, 2=0}
getWidth <<< maxWidth: 2
getWidth <<< depth: 3 position: 2
getWidth <<< depth: 3 position: 3
getWidth <<< depthLeftPosition: {1=0, 2=0, 3=3}
getWidth <<< maxWidth: 2
getWidth <<< depth: 4 position: 6
getWidth <<< depth: 4 position: 7
getWidth <<< depthLeftPosition: {1=0, 2=0, 3=3, 4=7}
getWidth <<< maxWidth: 2
getWidth <<< depth: 5 position: 14
getWidth <<< depth: 5 position: 15
main <<< widthOfBinaryTree: 2
main <<< depthLeftPosition: {1=0, 2=0, 3=3, 4=7}
The last screen capture shows a few (perhaps too many) test cases that I used to develop a solution to my initial problem and then to the one by LeetCode.
The first line holds the node values for a binary tree expressed in level order. The test scaffolding seems to process the input line, generate the associated binary tree, and then display the nodes executing a breadth first search traversal. The generated display of the binary tree (BT) seems to match the input line. All appears to be fine so far.
The next line displays the result of a function. The maximum width of a full BT with two levels is 2. More on this as we see the actual code.
The next line displays a 2, which is associated with the function that displays the maximum width of a specified BT. The tree may or may not be full or complete.
The following lines are for debugging purpose. Note that when done, the function seems to return as expected a 2. In this case we used a hash map that holds information for the first node at each level; in other words, the leftmost node. Note that the hash map is also displayed by the test scaffolding.
The second example is similar to the first with the difference that we use more nodes. In this BT we have 4 levels. The maximum width occurs at level 4 and happens to be 8.
As you can see in the three LeetCode examples, you can have different BTs for which all the results match and also others that do not match. The reason is in the difference on what makes up the width of a level.
My wife is calling me for lunch. Will pick up and finish this post as soon as I am done…
… I am back. We had pasta with a meat sauce. Lunch was good and did not take too long.
/**
* Definition for a binary tree node.
*/
class TreeNode {
// **** class members ****
int val;
TreeNode left;
TreeNode right;
// **** constructors ****
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
// **** ****
@Override
public String toString() {
return "" + this.val;
}
}
Good that I used the same class to represent tree nodes. I was able to slide into the LeetCode problem with little (if any) overhead. Not much to say about this class.
/**
* Test scaffolding.
*/
public static void main(String[] args) {
// **** BT root ****
TreeNode root = null;
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read data for BT (in level order) ****
String[] arr = sc.nextLine().split(",");
// **** close scanner ****
sc.close();
// **** populate the binary tree ****
// root = populateTree(arr);
root = populateBT(arr);
// ???? display the binary tree ????
System.out.println("main <<< bfsTraversal: ");
System.out.print(bfsTraversal(root));
// **** find and display the binary tree maximum width ****
System.out.println("main <<< maxBTWidth: " + maxBTWidth(root));
// **** compute and display the binary tree maximum width ****
System.out.println("main <<< widthOfBinaryTree1: " + widthOfBinaryTree1(root));
// **** compute and display the binary tree maximum width ****
System.out.println("main <<< widthOfBinaryTree: " + widthOfBinaryTree(root));
// ???? ????
System.out.println("main <<< depthLeftPosition: " + depthLeftPosition.toString());
}
This is the test scaffolding that I wrote for my problem. As we will see, the last two calls are for the LeetCode problem. The first one seems to work but is too slow. The second works and was accepted.
/**
* Generate the number of nodes in th eBT at the specified level.
*/
static int nodesInLevel(int level) {
if (level < 1)
return 0;
else
return (int)Math.pow(2.0, level - 1);
}
This is an auxiliary function. It returns the number of nodes in a full BT given the number of levels. If you try the first and second examples the function will return the proper number of nodes in those BTs.
/**
* Populate a binary tree using the specified array of integer and null values.
*/
static TreeNode populateBT(String[] arr) {
// **** auxiliary queue ****
Queue<TreeNode> q = new LinkedList<TreeNode>();
// **** ****
TreeNode root = null;
// **** begin and end of substring to process ****
int b = 0;
int e = 0;
// **** loop once per binary tree level ****
for (int level = 1; b < arr.length; level++) {
// ???? ????
// System.out.println("populateBT <<< level: " + level);
// **** count of nodes at this level ****
int count = nodesInLevel(level);
// ???? ????
// System.out.println("populateBT <<< count: " + count);
// **** compute e ****
e = b + count;
// ??? ????
// System.out.println("populateBT <<< b: " + b + " e: " + e);
// **** generate sub array of strings ****
String[] subArr = Arrays.copyOfRange(arr, b, e);
// ???? ????
// System.out.println("populateBT <<< subArr: " + Arrays.toString(subArr));
// **** populate the specified level in the binary tree ****
root = populateBTLevel(root, level, subArr, q);
// **** update b ****
b = e;
// ???? ????
// System.out.println("populateBT <<< b: " + b);
}
// **** return populated binary tree ****
return root;
}
This function is not part of the solution. I use it to load the BT from the input data in level order. The function makes a call to the populateBTLevel() which populates the specified level using the sub array generated from the provided data. The queue is used to collect the nodes for the next level.
/**
* Populate the specified level in the specified binary tree.
*/
static TreeNode populateBTLevel(TreeNode root, int level, String[] subArr, Queue<TreeNode> q) {
// **** populate binary tree root (if needed) ****
if (root == null) {
root = new TreeNode(Integer.parseInt(subArr[0]));
q.add(root);
return root;
}
// **** ****
TreeNode child = null;
// ???? ????
// System.out.println("populateBTLevel <<< subArr: " + Arrays.toString(subArr));
// **** traverse the sub array of node values ****
for (int i = 0; (i < subArr.length) && (subArr[i] != null); i++) {
// ???? ????
// System.out.println("populateBTLevel <<< q: " + q.toString());
// **** child node ****
child = null;
// **** create and attach child node (if needed) ****
if (!subArr[i].equals("null"))
child = new TreeNode(Integer.parseInt(subArr[i]));
// **** add child to the queue ****
q.add(child);
// **** attach child node (if NOT null) ****
if (child != null) {
if (insertChild == Child.LEFT)
q.peek().left = child;
else
q.peek().right = child;
}
// **** remove node from the queue (if needed) ****
if (insertChild == Child.RIGHT) {
// ???? ????
// System.out.println("populateBTLevel <<< q: " + q.toString());
q.remove();
}
// **** toggle insert for next child ****
insertChild = (insertChild == Child.LEFT) ? Child.RIGHT : Child.LEFT;
}
// ???? ????
// System.out.println("populateBTLevel <<< q: " + q.toString());
// **** return root of binary tree ****
return root;
}
This function is used to populate a level in the BT.
/**
* This function populates a BT in level order as specified by the array.
* This function supports 'null' values.
*/
static TreeNode populateTree(String[] arr) {
// ???? ????
// System.out.println("populateTree <<< arr: " + Arrays.toString(arr));
// **** root for the BT ****
TreeNode root = null;
// **** auxiliary queue ****
Queue<TreeNode> q = new LinkedList<TreeNode>();
// **** traverse the array of values inserting nodes
// one at a time into the BT ****
for (String strVal : arr) {
root = insertValue(root, strVal, q);
// ???? ????
// System.out.println("populateTree <<< q: " + q.toString());
}
// **** return the root of the binary tree ****
return root;
}
This function populates the BT in level order as specified by the array. Note that this is a different function to load the contents of a BT. Note that one of the methods to load the BT is commented out in the test scaffolding. I was just testing and experimenting on how to load the BT in order to get insights into the LeetCode problem.
/**
* Enumerate which child in the node at the head of the queue
* (see populateTree function) should be updated.
*/
enum Child {
LEFT,
RIGHT
}
// **** child turn to insert on node at head of queue ****
static Child insertChild = Child.LEFT;
As we have seen in previous posts, we use the enum and variable to decide which child to load in a node. We toggle this variable as we move from left to right on each tree level.
/**
* This function inserts the next value into the specified BT.
* This function is called repeatedly from the populateTree method.
* This function supports 'null' values.
*/
static TreeNode insertValue(TreeNode root, String strVal, Queue<TreeNode> q) {
// **** node to add to the BST in this pass ****
TreeNode node = null;
// **** create a node (if needed) ****
if (!strVal.equals("null"))
node = new TreeNode(Integer.parseInt(strVal));
// **** check is the BST is empty (this becomes the root node) ****
if (root == null)
root = node;
// **** add node to left child (if possible) ****
else if (insertChild == Child.LEFT) {
// **** add this node as the left child ****
if (node != null)
q.peek().left = node;
// **** for next pass ****
insertChild = Child.RIGHT;
}
// **** add node to right child (if possible) ****
else if (insertChild == Child.RIGHT) {
// **** add this node as a right child ****
if (node != null)
q.peek().right = node;
// **** remove node from queue ****
q.remove();
// **** for next pass ****
insertChild = Child.LEFT;
}
// **** add this node to the queue (if NOT null) ****
if (node != null)
q.add(node);
// **** return the root of the binary tree ****
return root;
}
This is the function called by the previous one. Both are used to load the contents of a BT. Of course, we just use one at a time.
/**
* This method implements a breadth-first search traversal of a binary tree.
* This method is iterative.
* It displays all nodes at each level on a separate line.
*/
static String bfsTraversal(TreeNode root) {
// **** to generate string ****
StringBuilder sb = new StringBuilder();
// **** define the current and next queues ****
List<TreeNode> currentQ = new LinkedList<TreeNode>();
List<TreeNode> nextQ = new LinkedList<TreeNode>();
// **** add the root node to the current queue ****
currentQ.add(root);
// **** loop while the current queue has entries ****
while (!currentQ.isEmpty()) {
// **** remove the next node from the current queue ****
TreeNode n = currentQ.remove(0);
// **** display the node value ****
if (n != null)
sb.append(n.toString() + " ");
else
sb.append("null ");
// **** add left and right children to the next queue ****
if (n != null) {
if (n.left != null)
nextQ.add(n.left);
else
nextQ.add(null);
if (n.right != null)
nextQ.add(n.right);
else
nextQ.add(null);
}
// **** check if the current queue is empty (reached end of level) ****
if (currentQ.isEmpty()) {
// **** end of current level ****
sb.append("\n");
// **** check if we have all null nodes in the next queue ****
boolean allNulls = true;
for (TreeNode t : nextQ) {
if (t != null) {
allNulls = false;
break;
}
}
// **** point the current to the next queue ****
currentQ = nextQ;
// **** clear the next queue ****
nextQ = new LinkedList<TreeNode>();
// **** clear the current queue (all null nodes) ****
if (allNulls)
currentQ = new LinkedList<TreeNode>();
}
}
// **** return a string representation of the BT ****
return sb.toString();
}
This function is used to traverse the BT in breadth first mode. We use it to display the contents of BTs after we load them. This function is part of the test scaffolding. It is not used in the solution.
/**
* Return the height of the specified BT.
* Increments height by 1 descending into the BT.
* This is a recursive call.
*/
static int treeDepth(TreeNode root) {
// **** base case ****
if (root == null)
return 0;
// **** height of left sub tree ****
int leftH = treeDepth(root.left) + 1;
// **** height of right sub tree ****
int rightH = treeDepth(root.right) + 1;
// **** return the largest height ****
return Math.max(leftH, rightH);
}
This is an auxiliary function that returns the height (or depth) of a BT.
/**
* Given a binary tree, write a function to get the maximum width of the given tree.
* Width of a tree is maximum of widths of all levels.
* Maximum complexity: O(n^2)
*/
static int maxBTWidth(TreeNode root) {
// **** ****
int maxWidth = Integer.MIN_VALUE;
int width = 0;
List<TreeNode> currentQ = new LinkedList<TreeNode>();
List<TreeNode> nextQ = new LinkedList<TreeNode>();
// **** prime the current queue ****
currentQ.add(root);
maxWidth = width = currentQ.size();
// ???? ????
// System.out.println("maxBTWidth <<< width: " + width + " maxWidth: " + maxWidth);
// **** loop while the current queue is not empty ****
while (!currentQ.isEmpty()) {
// **** remove head node from the current queue ****
TreeNode node = currentQ.remove(0);
// **** add left child to next queue (if needed) ****
if (node.left != null)
nextQ.add(node.left);
// **** add right child to next queue (if needed) ****
if (node.right != null)
nextQ.add(node.right);
// **** swap queues (if needed) ****
if (currentQ.isEmpty()) {
currentQ = nextQ;
nextQ = new LinkedList<TreeNode>();
// **** update the max width (if needed) ****
width = currentQ.size();
if (maxWidth < width)
maxWidth = width;
}
}
// **** ****
return maxWidth;
}
This function uses a BFS approach to the LeetCode problem. It seems to work for rather small BTs. It passed the example test cases. It times out during submission.
After some research I learned of a different approach to the problem. The following two functions including the two global variables, implement the solution that was accepted by LeetCode.
// **** global variables ****
static int maxWidth;
static HashMap<Integer, Integer> depthLeftPosition;
/**
* Auxiliary function.
* Recursive function.
*/
static void getWidth(TreeNode root, int depth, int position) {
// ???? ????
System.out.println("getWidth <<< depth: " + depth + " position: " + position);
// // **** base case ****
// if (root == null)
// return;
// **** add leftmost position to the hash map ****
depthLeftPosition.computeIfAbsent(depth, mappingFunction->position);
// ???? ????
System.out.println("getWidth <<< depthLeftPosition: " + depthLeftPosition.toString());
// **** update the max width ****
maxWidth = Math.max(maxWidth, position - depthLeftPosition.get(depth) + 1);
// ???? ????
System.out.println("getWidth <<< maxWidth: " + maxWidth);
// **** recursive cases (base case included) ****
if (root.left != null)
getWidth(root.left, depth + 1, position * 2);
if (root.right != null)
getWidth(root.right, depth + 1, position * 2 + 1);
}
In this case we use two global variables. One holds the maximum width and the other holds the depth left position of the nodes on the specified level. Take a look at the examples and following the code see how the hash map is used. After the first level, the leftmost node, which happens to be the root node, is the leftmost and it is located in the first (and only) node at level 1.
After processing the second level, the hash map holds in addition the 
leftmost start node for level 2. The idea behind is to assign positions to the nodes which match the ones in a full and complete BT. The first example illustrates this with nodes 1 to 3. The second example shows the software processing a full and complete BT of 4 levels.
The idea is to compute the maximum distance between the position of the leftmost and the rightmost nodes in each level. That would address the requirements in the LeetCode problem. Note that we compute on the fly the rightmost position per level so we do not need to store it.
The rest of the recursive process is to visit the rest of the nodes at the specified depth and position. At each level we do something similar to what was done in my original approach. We get the two end nodes in a level and get the maximum width.
/**
* Given a binary tree, write a function to get the maximum width of the given tree.
* The maximum width of a tree is the maximum width among all levels.
*
* The width of one level is defined as the length between the end-nodes
* (the leftmost and right most non-null nodes in the level,
* where the null nodes between the end-nodes are also counted into the length calculation.
*
* It is guaranteed that the answer will in the range of 32-bit signed integer.
*/
static int widthOfBinaryTree(TreeNode root) {
// **** initialize global variable(s) ****
maxWidth = 0;
depthLeftPosition = new HashMap<Integer, Integer>();
// **** start recursion ****
getWidth(root, 1, 0);
// **** return answer ****
return maxWidth;
}
This is the entry point for the function in the LeetCode example. We initialize variables and then recursively update the maximum width. When done we return the value stored in the global variable.
/**
* Given a binary tree, write a function to get the maximum width of the given tree.
* The maximum width of a tree is the maximum width among all levels.
*
* The width of one level is defined as the length between the end-nodes
* (the leftmost and right most non-null nodes in the level,
* where the null nodes between the end-nodes are also counted into the length calculation.
*
* It is guaranteed that the answer will in the range of 32-bit signed integer.
*/
static int widthOfBinaryTree1(TreeNode root) {
// **** local variables ****
int level = 1;
int width = 1;
List<TreeNode> currentQ = new LinkedList<TreeNode>();
List<TreeNode> nextQ = new LinkedList<TreeNode>();
// **** initialize global variable(s) ****
maxWidth = 0;
// **** get the depth of the binary tree ****
int depth = treeDepth(root);
// ???? ????
// System.out.println("widthOfBinaryTree <<< depth: " + depth);
// **** prime the current queue ****
currentQ.add(root);
// **** loop while the current queue is not empty ****
while (!currentQ.isEmpty() && (level <= depth)) {
// ???? ????
// System.out.println("widthOfBinaryTree <<< level: " + level + " currentQ: " + currentQ.toString());
// **** remove head node from the current queue ****
TreeNode node = currentQ.remove(0);
// **** process this node ****
if (node == null) {
nextQ.add(null);
nextQ.add(null);
} else {
// **** add left child to next queue (if needed) ****
if (node.left != null)
nextQ.add(node.left);
else
nextQ.add(null);
// **** add right child to next queue (if needed) ****
if (node.right != null)
nextQ.add(node.right);
else
nextQ.add(null);
}
// **** swap queues (if needed) ****
if (currentQ.isEmpty()) {
// ???? ????
// System.out.println("widthOfBinaryTree <<< level: " + level + " width: " + width + " maxWidth: " + maxWidth);
// **** update max width (if needed) ****
if (width > maxWidth)
maxWidth = width;
// **** swap queues ****
currentQ = nextQ;
nextQ = new LinkedList<TreeNode>();
// **** incremment level ****
level++;
// **** compute the width for the next level (if needed) ****
if (level <= depth)
width = levelWidth(currentQ);
}
}
// **** return the max width of the binary tree ****
return maxWidth;
}
This is my initial function to solve the LeetCode problem. It times out.
/**
* Determine the width of the binary tree based on the contents of the queue.
* Complexity: O(n)
*/
static int levelWidth(List<TreeNode> q) {
// **** ****
int first = 0;
int last = 0;
// **** look for first non-null node ****
for (int i = 0; i < q.size(); i++) {
if (q.get(i) != null) {
first = i;
break;
}
}
// **** look for last non-null node ****
for (int i = q.size() - 1; i >= 0; i--) {
if (q.get(i) != null) {
last = i;
break;
}
}
// **** return the width ****
return last - first + 1;
}
This function performs operations to the specified queue which is filled when the previous level is processed. I was thinking by calling this function I would be able to get the value required by LeetCode. It works but the combination of functions is too slow to be accepted.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address: john.canessa@gmail.com. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!
One last thing, many thanks to all 1824 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
Twitter: @john_canessa