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

Binary Tree Right Side View

Explore how to determine the right side view of a binary tree by using depth-first search. This lesson helps you learn to traverse trees recursively, identify rightmost nodes at each level, and analyze the time and space complexity of the solution.

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

Swift
import Swift



func rightSideView(root: TreeNode?) -> [Int] {

    return []

}
Right-side view of binary tree exercise

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:

Swift
import Swift
func DFS(node: TreeNode?, level: Int, rightside: inout [Int]) {
    if level == rightside.count { 
        rightside.append(node!.val)
    }
    
    if node!.right != nil { 
        DFS(node: node!.right, level: level + 1, rightside: &rightside)
    }  
    if node!.left != nil { 
        DFS(node: node!.left, level: level + 1, rightside: &rightside)
    }
}    
    
func rightSideView(root: TreeNode?) -> [Int] {
    if root == nil { return [] }
    
    var rightside: [Int] = []
    DFS(node: root, level: 0, rightside: &rightside);
    
    return rightside
}
func Print(vec: [Int]){
    var to_print: String =  "["
    var i: Int = 0
    while i < vec.count {
        to_print += String(vec[i])
        if i + 1 < vec.count {
            to_print += ", "
        }
        i += 1
    }
    to_print += "]"
    print(to_print)
}
    // Driver Code
    let root: TreeNode = TreeNode(x: 1)
    root.left = TreeNode(x: 2)
    root.right = TreeNode(x: 3)
    root.left!.left = TreeNode(x: 4)
    root.left!.right = TreeNode(x: 5)
    root.right!.left = TreeNode(x: 6)
    root.right!.right = TreeNode(x: 7)
    root.right!.right!.left = TreeNode(x: 8)
    let res: [Int] = rightSideView(root: root)
    Print(vec: res)
Right-side view of binary tree solution

Complexity measures

Time Complexity
...