Java Algorithms: Coding a Binary Tree Right Side View (LeetCode)

Task description:

Given the root of a binary tree, imagine yourself standing on the right side of it. Then, return the values of the nodes you can see ordered from top to bottom.

Example 1:

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

Example 2:

Input: root = [1,null,3]
Output: [1,3]

Example 3:

Input: root = []
Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Reasoning:

I would say it’s a pretty popular question during coding interviews. At the first glance, it seems like it’s pretty easy and straightforward to implement. It’s a false feeling. You think so because of provided example. Let me show you some other examples that aren’t as easy.

First Example

What do you think about this example? Is a viable path still that obvious to you? If your answer is yes, let me try again.

Second Example

Is it still that obvious? I don’t think so. If you don’t agree with me, it’s probably a good idea to skip the rest of this piece. For those of you who are confused, stay with me.

Let’s introduce the concept of level:

Levels of a Binary Tree

Using simple words — think of the level for a particular node in a binary tree as the depth of that node. You could also think of it as — how many steps down you need to make, starting from the root of the tree, in order to get to a particular node.

I think at this moment you might’ve realized that we need to walk through every single node in a provided binary tree, and for each node, we need to answer just one question. Is this node the right one on its level? It’s simple as that.

Solution:

I’m going to explain the solution using a recursive approach. We need to introduce a collection for storing our answers.

List<Integer> result = new ArrayList<>();
if (root == null)
{
   return result;
}

We can immediately return an empty collection if we got a null root node.

I also introduce a HashMap for storing information whether or not we visited a particular level

Map<Integer, Boolean> visited = new HashMap<>();

It’s time to introduce the recursive method with the main logic in it.

private void rightSideView(TreeNode root, List<Integer> result, Map<Integer, Boolean> visited, int currentLevel)
{
   if (root == null)
   {
      return;
   }

   if (!visited.getOrDefault(currentLevel, false))
   {
      visited.put(currentLevel, true);
      result.add(root.val);
   }
   rightSideView(root.right, result, visited, currentLevel + 1);
   rightSideView(root.left, result, visited, currentLevel + 1);
}

3 things in the method are important:

1. We need to stop exploring trees at some point, we do it if the node we reached is null

2. When we visit a node we want to check if it’s the best choice at the specific level. If so, we store it and add this node to our collection which stores the answer.

3. The way we explore the tree is also important. You might have already guessed that as long as we are asked to provide the best fit node at each level, we will often choose to go to the right child of the current node first and after that go to the left.

   
   

The full solution is this

public List<Integer> rightSideView(TreeNode root)
{
   List<Integer> result = new ArrayList<>();
   if (root == null)
   {
      return result;
   }

   Map<Integer, Boolean> visited = new HashMap<>();
   rightSideView(root, result, visited, 1);

   return result;
}

private void rightSideView(TreeNode root, List<Integer> result, Map<Integer, Boolean> visited, int currentLevel)
{
   if (root == null)
   {
      return;
   }

   if (!visited.getOrDefault(currentLevel, false))
   {
      visited.put(currentLevel, true);
      result.add(root.val);
   }
   rightSideView(root.right, result, visited, currentLevel + 1);
   rightSideView(root.left, result, visited, currentLevel + 1);
}

This code gives us linear time and space complexity, and it performs pretty well.

See you in the next articles 🙃🙃🙃🙃🙃🙃🙃🙃🙃🙃🙃🙃🙃🙃🙃

Also published here.