## Balance a Binary Search Tree

Good evening. It is Tuesday January 12, 2021. We are still in the middle of the COVID-19 pandemic. For some reason vaccination in the USA and specific in Minnesota is not progressing at a reasonable pace. Hopefully when all political issues clear, things will start progressing at a better pace. Continue reading “Balance a Binary Search Tree”

## Largest Triple Products

Once again it is Friday during the COVID-19 pandemic. Not much to say due to the fact that outside work not much is changing. So far the COVID-19 vaccine development programs appear to be moving forward. Earlier this week UK started vaccinating people in nursing homes.

One of the sons of my best friend was married last year and moved to the UK. His wife and he had a baby boy about three months ago. My friendâ€™s son, his spouse and newborn arrived earlier today for a month long visit. Hope they have a great time. Hopefully a month from now with the help of vaccines things will be getting better all over the world. Continue reading “Largest Triple Products”

## Reverse Operations

In the past three days the high for the day has been in the mid to upper 40s. Since late fall a considerable amount of leaves has been accumulating in the entrance at home. Yesterday just before lunch I picked up the dead leaves. This morning some started to collect. I guess this is due to the orientation and shape of the entrance.

Last evening I also read an interesting article titled After Centuries, a Seemingly Simple Math Problem Gets an Exact Solution by Steve Nadis published in Quanta Magazine. Apparently a German mathematician named Ingo Ullisch figured out an exact solution for a problem. Good for him. What I liked more than the problem or its solution is the last paragraph in the article. In my humble opinion, this reaffirms the fact that reading and experimenting is the best way to learn. Continue reading “Reverse Operations”

## Number of Visible Nodes

!!! UPDATE – UPDATE – UPDATE !!!

I have been asked several questions on this post. Given that you are not able to submit your solution and be tested against dozens of test cases in order to determine [1] if you have properly understood the problem or [2] generated an acceptable solution to the properly understood problem.

Since there is no interviewer at hand that you can ask questions to clarify the problem, please read the requirements and decide what the requirements are.

```There is a binary tree with N nodes.
You are viewing the tree from its left side and can see only the leftmost nodes at each level.
Return the number of visible nodes.

Note: You can see only the leftmost nodes, but that doesn't mean they have to be left nodes.
The leftmost node at a level could be a right node.

Input
The root node of a tree, where the number of nodes is between 1 and 1000,
and the value of each node is between 0 and 1,000,000,000

An int representing the number of visible nodes.
```

MY INTERPRETATION is that when I view the tree from the left side I will be looking at the first visible node in each level. The node may be a right or a left child. The note in the description seems to corroborate my thoughts.

MY APPROACH is to perform a DFS traversal. The node we can see from the left will be the first non-null node at each level. In addition, we could get the depth of the tree and it should provide the SAME answer given that no matter which side we look from (left or right) the same number of nodes should be visible.

```3,null,5,7,null
main <<< arr: [3, null, 5, 7, null]
main <<< bfs:
3
null 5
7 null
main <<< visibleNodes: 3
main <<<        depth: 3
main <<< bfs (no null nodes):
3
5
7
main <<<        level: 3

3,2,5,1,4
main <<< arr: [3, 2, 5, 1, 4]
main <<< bfs:
3
2 5
1 4 null null
main <<< visibleNodes: 3
main <<<        depth: 3
main <<< bfs (no null nodes):
3
2 5
1 4
main <<<        level: 3

8
3 10
1 6 null 14
null null 4 7 null null
main <<< visibleNodes: 4
main <<<        depth: 4
main <<< bfs (no null nodes):
8
3 10
1 6 14
4 7
main <<<        level: 4

1,2,3,null,5,null,7
main <<< arr: [1, 2, 3, null, 5, null, 7]
main <<< bfs:
1
2 3
null 5 null 7
main <<< visibleNodes: 3
main <<<        depth: 3
main <<< bfs (no null nodes):
1
2 3
5 7
main <<<        level: 3

5
4 8
11 null 17 4
7 null null null 5 null
main <<< visibleNodes: 4
main <<<        depth: 4
main <<< bfs (no null nodes):
5
4 8
11 17 4
7 5
main <<<        level: 4

5
4 8
11 null 17 4
7 null null null 5 null
main <<< visibleNodes: 4
main <<<        depth: 4
main <<< bfs (no null nodes):
5
4 8
11 17 4
7 5
main <<<        level: 4

5,4,8,11,null,17,4,7,null,null,null,5,null,null,null,20,30
main <<< arr: [5, 4, 8, 11, null, 17, 4, 7, null, null, null, 5, null, null, null, 20, 30]
main <<< bfs:
5
4 8
11 null 17 4
7 null null null 5 null
null null 20 30
main <<< visibleNodes: 5
main <<<        depth: 5
main <<< bfs (no null nodes):
5
4 8
11 17 4
7 5
20 30
main <<<        level: 5

5,4,8,11,null,17,4,7,null,null,null,5,null,null,null,20,30,100,101,102,103
main <<< arr: [5, 4, 8, 11, null, 17, 4, 7, null, null, null, 5, null, null, null, 20, 30, 100, 101, 102, 103]
main <<< bfs:
5
4 8
11 null 17 4
7 null null null 5 null
null null 20 30
100 101 102 103
main <<< visibleNodes: 6
main <<<        depth: 6
main <<< bfs (no null nodes):
5
4 8
11 17 4
7 5
20 30
100 101 102 103
main <<<        level: 6

1,2,3,4,5,6,7,null,null,null,null,null,null,null,8,null,9,10,null
main <<< arr: [1, 2, 3, 4, 5, 6, 7, null, null, null, null, null, null, null, 8, null, 9, 10, null]
main <<< bfs:
1
2 3
4 5 6 7
null null null null null null null 8
null 9
10 null
main <<< visibleNodes: 6
main <<<        depth: 6
main <<< bfs (no null nodes):
1
2 3
4 5 6 7
8
9
10
main <<<        level: 6

8,3,10,1,6,null,14,null,null,4,7,13
main <<< arr: [8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13]
main <<< bfs:
8
3 10
1 6 null 14
null null 4 7 13 null
main <<< visibleNodes: 4
main <<<        depth: 4
main <<< bfs (no null nodes):
8
3 10
1 6 14
4 7 13
main <<<        level: 4

8,3,10,1,6,null,14,null,null,4,7,13,15
main <<< arr: [8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13, 15]
main <<< bfs:
8
3 10
1 6 null 14
null null 4 7 13 15
main <<< visibleNodes: 4
main <<<        depth: 4
main <<< bfs (no null nodes):
8
3 10
1 6 14
4 7 13 15
main <<<        level: 4

10,null,15,null,5
main <<< arr: [10, null, 15, null, 5]
main <<< bfs:
10
null 15
null 5
main <<< visibleNodes: 3
main <<<        depth: 3
main <<< bfs (no null nodes):
10
15
5
main <<<        level: 3
```

The test cases contain tree values. The first is the one returned by performing a BFS tree traversal and counting the number of levels. The second is a method that returns the depth of the tree. The third pass is a BFS traversal so we can count the nodes we see from the right or left in the binary tree. The null values are no longer displayed because they do not exist as far as nodes in a binary tree. Unless I am missing something; all values should be the same.

```    /**
* Test scaffolding.
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {

// **** open buffered stream ****

// **** read and split input line ****

// **** close buffered reader ****
input.close();

// **** create and populate integer array (may contain null) ****
Integer[] arr = new Integer[strArr.length];
for (int i = 0; i < strArr.length; i++) {
if (strArr[i].equals("null"))
arr[i] = null;
else
arr[i] = Integer.parseInt(strArr[i]);
}

// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));

// **** create and populate binary tree ****
TreeNode root = populateTree(arr);

// ???? ????
System.out.println("main <<< bfs:");
System.out.print(bfsTraversal(root));

// **** compute and display number of visible node ****
System.out.println("main <<< visibleNodes: " + visibleNodes(root));

// **** find and display the depth of the BT ****
System.out.println("main <<<        depth: " + maxDepth(root));

// **** find and display level of BT ****
System.out.println("main <<< bfs (no null nodes): ");
System.out.println("main <<<        level: " + levelOrderTraversal(root));
}
```

This is the test case. I believe this is the same as in the original post but with an additional computation.

```    /**
* Count visible nodes in binary tree.
* Recursive call.
* O(n)
*/
static int visibleNodes(TreeNode root) {

// **** base condition ****
if (root == null) return 0;

// **** recursive call(s) ****
return Math.max(visibleNodes(root.left) + 1, visibleNodes(root.right) + 1);
}
```

This is the same code as in the original post. It returns the number of visible nodes including some of the null values which indicate the place of a missing node.

```    /**
* Given a binary tree, find its maximum depth.
* Recursive function O(log(n)).
*/
static int maxDepth(TreeNode root) {

// **** base condition ****
if (root == null)
return 0;

// **** initialize the BT max depth ****
int depth = 0;

// **** visit left node ****
depth = Math.max(depth, maxDepth(root.left) + 1);

// **** visit right node ****
depth = Math.max(depth, maxDepth(root.right) + 1);

// **** return the max depth ****
return depth;
}
```

Compute the max depth of a binary tree.

```    /**
* Display the nodes in a binary tree per level.
* This function returns the number of levels in the
* specified binary tree.
*/
static int levelOrderTraversal(TreeNode root) {

// **** ****
int level = 0;

// **** prime q ****

// **** loop while q is not empty ****
while (!q.isEmpty()) {

// **** remove head node ****
TreeNode tempNode = q.poll();

// **** display the value of this node ****
System.out.print(tempNode.val + " ");

// **** enqueue left child ****
if (tempNode.left != null)

// **** enqueue right child ****
if (tempNode.right != null)

// **** check if q is empty (end of level) ****
if (q.isEmpty()) {

// **** end the current level ****
System.out.println();

// **** increment level ****
level++;

// **** swap queues ****
q = t;
}
}

// **** return binary tree level ****
return level;
}
```

This method performs a BFS depth traversal of the tree. It displays the values of existing nodes. The placeholders for null nodes are not displayed. In addition the function counts the levels in the tree. When done the number of levels are returned. This value should match the other two values generated by the previous functions.

Looking at the output of this last function you can see that when looking at the tree from the left or from the right the number of levels should be the same. What may change is the value of the nodes when looked from the left or right sides. Note that the requirements do not make reference to the actual values of the nodes; we just care for the count.

In addition you may draw the circumferences representing the nodes in a 2D space. If you look at the binary tree from the left of the right you should just see the end lines of the end nodes which represent the diameter of the nodes. At that time disregard the links connecting nodes and count the number of nodes you see from either side. They should be the same and match all three results per test case.

Hope this is of help!

!!! NOW BACK TO THE ORIGIONAL POST!!!

Good day! Hope you are doing well. Apparently the number of COVID-19 cases in the Twin Cities of Minneapolis and St. Paul has risen. In addition it seems that the number of free ICU beds had dropped closely to 0. This implies that a person who falls sick and needs intensive care might have a tough time finding an available bed. For our own sake, please follow distancing rules and keep safe. We all will benefit from such behavior.

I have been looking at some problems in a Facebook portal. They are intended as exercises for technical interviews. Continue reading “Number of Visible Nodes”