Search⌘ K
AI Features
Home
Courses
Decode the Coding Interview in Scala: Real-World Examples

Binary Tree Right Side View

Explore how to determine the right side view of a binary tree by identifying rightmost nodes at each level. Learn to implement a depth-first search approach and understand the associated time and space complexities for efficient traversal.

We'll cover the following...

Description

You are given a binary tree T. Imagine you are standing to the right of it; you have to return the value of the nodes you can see from top to bottom.

You have to return the rightmost nodes on their respective levels in the form of an array.

Let’s discuss an example below:

Coding exercise

Scala
class TreeNode(var value:Int=0, var left:TreeNode=null, var right:TreeNode=null) {
}
object Solution {
  def rightSideView(root: TreeNode): Array[Int] = {
    // write your code here
    Array[Int]()
  }
}
Binary tree right side view

Solution

We can use a depth-first search (DFS) to solve this problem. The intuition here is to traverse the tree level by level recursively, starting from the rightmost node for each recursive call.

Let’s review the implementation below:

Scala
import scala.collection.mutable.ListBuffer
object Main {
  class TreeNode(var value:Int=0, var left:TreeNode=null, var right:TreeNode = null){
  }
  def DFS(node: TreeNode, level: Int, rightside: ListBuffer[Int]): Unit = {
    if (level == rightside.size) rightside.addOne(node.value)
    if (node.right != null) DFS(node.right, level + 1, rightside)
    if (node.left != null) DFS(node.left, level + 1, rightside)
  }
  def rightSideView(root: TreeNode): ListBuffer[Int] = {
    val rightside = new ListBuffer[Int]
    if (root == null) return rightside
    DFS(root, 0, rightside)
    rightside
  }
  def main(args: Array[String]): Unit = {
    val root = new TreeNode(1)
    root.left = new TreeNode(2)
    root.right = new TreeNode(3)
    root.left.left = new TreeNode(4)
    root.left.right = new TreeNode(5)
    root.right.left = new TreeNode(6)
    root.right.right = new TreeNode(7)
    root.right.right.left = new TreeNode(8)
    println("" + rightSideView(root))
  }
}
Binary tree right side view

Complexity measures

Time Complexity
...