Decode the Coding Interview in Go: Real-World Examples/

...

/

Binary Tree Right Side View

Binary Tree Right Side View

Understand and solve the interview question "Binary Tree Right Side View".

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:

Do it yourself

package main
import (
  "fmt"
  "strconv"
  "encoding/json"
)
type TreeNode struct{
    val int
    left *TreeNode
    right *TreeNode
}
func rightSideView(root *TreeNode) []int {
    // write your code here
    return []int{}
}
Right-Side View of Binary Tree

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:

package main
import (
  "fmt"
  "strconv"
)
type TreeNode struct{
    val int
    left *TreeNode
    right *TreeNode
}
func DFS(node *TreeNode, level int, rightside *[]int) {
    if level == len((*rightside)) {
        (*rightside) = append((*rightside), node.val)
    }
    
    if node.right != nil {
        DFS(node.right, level + 1, rightside);
    }
    if (node.left != nil) {
        DFS(node.left, level + 1, rightside)
    }
}    
    
func rightSideView(root *TreeNode) []int {
    var rightside []int
    if root == nil {
        return rightside
    }
    
    DFS(root, 0, &rightside)
    
    return rightside
}
func main() {
    // Driver code
    root := &TreeNode{val: 1}
    root.left = &TreeNode{val: 2}
    root.right = &TreeNode{val: 3}
    root.left.left = &TreeNode{val: 4}
    root.left.right = &TreeNode{val: 5}
    root.right.left = &TreeNode{val: 6}
    root.right.right = &TreeNode{val: 7}
    root.right.right.left = &TreeNode{val: 8}
    print(rightSideView(root))
}
Right-Side View of Binary Tree

Complexity measures

Time Complexity
...