The right view of a binary tree is a list of nodes that are visible when the tree is viewed from the right side. In other words, it is a list of the last node in each level of the tree when viewed from the right.
Here’s an example binary tree:
1
/ \
2 3
\ \
4 5
/ \ / \
6 7 8 9The right view of this tree would be [1, 3, 5, 9], because those are the nodes that are visible when the tree is viewed from the right side.
To obtain the right view of a binary tree, we can use a similar approach to the left view. Instead of adding the first node of each level to the list, we add the last node of each level. We can do this by traversing the tree level by level from right to left, and adding the last node of each level to the result list.
Here’s an example Kotlin function that implements this approach:
fun rightView(root: TreeNode?): List<Int> {
val rightView = mutableListOf<Int>()
if (root == null) {
return rightView
}
val queue = ArrayDeque<TreeNode>()
queue.addLast(root)
while (queue.isNotEmpty()) {
val levelSize = queue.size
for (i in 0 until levelSize) {
val node = queue.removeFirst()
if (i == levelSize - 1) {
rightView.add(node.`val`)
}
node.left?.let { queue.addLast(it) }
node.right?.let { queue.addLast(it) }
}
}
return rightView
}The rightView function takes a binary tree node root as input and returns a list of integers representing the right view of the binary tree.
The function first creates an empty mutable list called rightView. If the input root is null, it immediately returns the empty rightView list.
If the input root is not null, the function creates a queue called queue to store the nodes to be processed in a level-wise manner. It starts by adding the root node to the queue.
The function then enters a while loop that continues until the queue is empty. In each iteration of the loop, the function processes one level of the binary tree. It first determines the number of nodes in the current level by getting the size of the queue (which should be the number of nodes currently in the queue). It then loops through the nodes in the current level by iterating from 0 until levelSize - 1.
For each node in the current level, the function removes it from the front of the queue using queue.removeFirst(), and checks if it is the last node in the level by comparing i to levelSize - 1. If it is the last node in the level, it adds its value to the rightView list using rightView.add(node.val).
The function then checks if the node has any non-null children, and if it does, adds them to the end of the queue using queue.addLast(). Note that the function adds the right child first, followed by the left child, so that the nodes in the current level are processed from right to left.
Once all the nodes in the current level have been processed, the function loops back to the beginning of the while loop to process the next level, if there are any remaining nodes in the queue.
Finally, once the queue is empty, the function returns the rightView list, which should contain the values of the last node in each level of the binary tree when viewed from the right side.
class TreeNode(var `val`: Int) {
var left: TreeNode? = null
var right: TreeNode? = null
}
fun rightView(root: TreeNode?): List<Int> {
val rightView = mutableListOf<Int>()
if (root == null) {
return rightView
}
val queue = ArrayDeque<TreeNode>()
queue.addLast(root)
while (queue.isNotEmpty()) {
val levelSize = queue.size
for (i in 0 until levelSize) {
val node = queue.removeFirst()
if (i == levelSize - 1) {
rightView.add(node.`val`)
}
node.left?.let { queue.addLast(it) }
node.right?.let { queue.addLast(it) }
}
}
return rightView
}
fun main() {
// Create example binary tree
val root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left?.right = TreeNode(4)
root.right?.right = TreeNode(5)
root.left?.right?.left = TreeNode(6)
root.left?.right?.right = TreeNode(7)
root.right?.right?.left = TreeNode(8)
root.right?.right?.right = TreeNode(9)
// Obtain right view of tree
val rightView = rightView(root)
// Print right view
println("Right view of tree: $rightView")
}main function, we first create an example binary tree with the same structure as the one shown in the previous example. We then call the rightView function to obtain the right view of the tree, and store the result in the rightView variable. Finally, we print the right view of the tree using println.
When we run this main function, we should see the following output : Right view of tree: [1, 3, 5, 9]