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 ****
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

        // **** read and split input line ****
        String[] strArr = input.readLine().split(",");

        // **** 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) {

        // **** ****
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        Queue<TreeNode> t = new LinkedList<TreeNode>();
        int level = 0;

        // **** prime q ****
        q.add(root);

        // **** 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)
                t.add(tempNode.left);
 
            // **** enqueue right child ****
            if (tempNode.right != null)
                t.add(tempNode.right);

            // **** 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;
                t = new LinkedList<TreeNode>();
            }
        }

        // **** 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.

It seems that you have to use the editor they provide. It does not have intelligent auto completion features. In most (never say all) IDEs (e.g., Eclipse, VSCode) when you request a class to be included, the associated library is automatically added to your source code. Not sure what is the point of using such a simple and basic IDE.

As far as the problem decryptions of the problems, some are relatively well explained while others are harder to understand. I have a hard time understanding why problems are not well defined. It goes against software engineering principles and practices. You should not start solving a problem until you understand what is required. That said, so far, in a couple problems that I have attempted (will be posting one at a time in the next few days) you can ask for hints. It seems that about three hints are provided. I tried one in one of the problems. It made a difference.

One last thing; at the site, you can compile and run the code. Very few test cases (2 or 3) are available per problem. The bad thing is that you might get a solution candidate that works with the test cases, yet fails when you try more advanced tests that you create on your own.

I will continue experimenting with the site for one more week or so. At that time I will go back to HackerRank and LeetCode. Each solution is submitted to many tests so you can be confident that your approach is solid.

The problem Number of Visible Nodes can be found here.

It should be of no surprise to you that I have decided to use Java to solve the problem. I had to generate my own test scaffolding. I used a Windows 10 machine and the VSCode IDE. Hopefully software engineers at Facebook are using state of the art IDEs.

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

Output:

An int representing the number of visible nodes.

Please read the problem description and see if you can come up witch the actual requirements…

…We have a binary tree (not a BST). You are viewing the tree from the left side. Of course that is not possible because binary trees are not three dimensional. So when you read that you can only see the leftmost nodes at each level, you have to assume that you can see at least one (in this case probably the leftmost) node per level.

The note that follows clarifies our dilemma. We need to compute the depth of a binary tree.

The input is a binary tree. The number of nodes and the values of the nodes are specified. I did not see an issue so far.

We need to compute the depth of the binary tree and return it to the caller.

int visibleNodes(Node root) {
}

The description of the problem seems to match the expected argument. So far so good!

3,2,5,1,4
main <<< arr: [3, 2, 5, 1, 4]
main <<< bfs:
3 
2 5
1 4 null null
main <<< visibleNodes: 3


8,3,10,1,6,null,14,null,null,4,7
main <<< arr: [8, 3, 10, 1, 6, null, 14, null, null, 4, 7]
main <<< bfs:
8
3 10
1 6 null 14
null null 4 7 null null
main <<< visibleNodes: 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


5,4,8,11,null,17,4,7,null,null,null,5
main <<< arr: [5, 4, 8, 11, null, 17, 4, 7, null, null, null, 5]
main <<< bfs:
5 
4 8
11 null 17 4
7 null null null 5 null
main <<< visibleNodes: 4


5,4,8,11,null,17,4,7,null,null,null,5,null
main <<< arr: [5, 4, 8, 11, null, 17, 4, 7, null, null, null, 5, null]
main <<< bfs:
5
4 8
11 null 17 4
7 null null null 5 null
main <<< visibleNodes: 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


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


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


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


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

Sorry if I went overboard with the test cases. Allow me to explain. I had a not too well optimized set of functions that I use when parsing the nodes of a binary tree provided as a single line of a breadth first traversal on the tree. This approach is quite common in LeetCode. I decided to optimize and clean up the code. I will not cover the test scaffolding in this post. If interested please take a look at the code in my GitHub repository.

Let’s discuss what we see per test case. We are provided a line with the results of a depth first traversal of a binary tree. Note that the first example does not contain null values. In contrast, the second example contains some null values.

Our test scaffolding seems to parse the values and places them into an array. This will become obvious when we see the code. We then display the binary tree using a breadth first search approach. We can see that our first binary tree has three levels. One way or the other, no matter our viewpoint, we should be able to imagine that at least one node in a level will be viewed from the left or right side. Our second test case seems to contain 4 levels.

If you have any doubts about what we have done so far, please take a piece of paper and pencil and make sure you can draw the binary tree associated with the specified input string.

    /**
     * Test scaffolding.
     * 
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered reader ****
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

        // **** read and split input line ****
        String[] strArr = input.readLine().split(",");

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

        // **** create and populate integer array ****
        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 answer ****
        System.out.println("main <<< visibleNodes: " + visibleNodes(root));
    }

Our test scaffolding, which IS NOT PART OF THE SOLUTION, uses a buffered reader to read the line with the nodes for the binary tree. We then create an array of integer and assign the values we read from the input. We display the array to make sure all is well so far.

We then use the array of integers to create the binary tree we will be processing. To give us a better idea on the tree and check that all is going well, we display the binary tree using a depth first search approach. You should be able to map the values in the input line to the output of the bfs traversal function / method. Once again, if you have doubts, take some time and make sure you agree with what we have covered so far…

…OK, we are now ready to develop the code for the solution. Before we do so, please think of the idea for our approach. We will compute the depth of a binary tree.

    /**
     * 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);
    }

In production I do not like to develop such small code. It is somewhat harder to follow. That said; let’s think about what we need to do and what the code does.

The recursive call returns a 0 when we reach a leaf node. This is our base condition and we return 0. Draw a simple three node binary tree and follow the code. When we reach a leaf node, we start going up the stack. Note that the recursive calls add 1 to the returned value. At each node, we perform a tree traversal on the left and the right sub trees. The returned values are checked so we return the highest. There are not too many ways you can draw a binary tree with 3 nodes. Experiment with them using the suggested algorithm. It seems to work well.

Since we Facebook web site does not provide tons of test cases, the code I am suggesting might have issues. If this is the case, please send me a message of leave me your thoughts in the comment section of this post.

Hope you enjoyed solving this problem as much as I did. 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 help out 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 e-mail message. 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 4,785 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy.

John

john.canessa@gmail.com