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

Binary Tree Right Side View

Explore how to obtain the right side view of a binary tree by applying depth-first search in Rust. This lesson guides you through recursive traversal from the rightmost nodes and explains the associated time and space complexities, equipping you to solve similar tree-based coding interview problems confidently.

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

Rust 1.57.0
fn right_side_view(root: Option<Rc<RefCell<TreeNode>>>)-> Vec<i32>{
    
    return vec![];
}

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:

Rust 1.57.0
fn right_side_view(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut res = Vec::new();
        let mut curlevel = 0;
        if root.is_none() {
            return res;
        }
        let mut dq = VecDeque::new();
        dq.push_back((0, root.clone()));
        res.push(root.as_ref().unwrap().borrow().val);
        while !dq.is_empty() {
            if let Some((level, Some(node))) = dq.pop_front() {
                dq.push_back((level + 1, node.borrow().right.clone()));
                dq.push_back((level + 1, node.borrow().left.clone()));
                if level > curlevel {
                    res.push(node.borrow().val);
                    curlevel = level;
                }
            }
        }
        res
    }
fn main() {
    let mut root = TreeNode::new(1);
    root.left = Some(Rc::new(RefCell::new(TreeNode::new(2))));
    root.right = Some(Rc::new(RefCell::new(TreeNode::new(3))));
    root.left.clone().unwrap().borrow_mut().left = Some(Rc::new(RefCell::new(TreeNode::new(4))));
    root.left.clone().unwrap().borrow_mut().right = Some(Rc::new(RefCell::new(TreeNode::new(5))));
    root.right.clone().unwrap().borrow_mut().left = Some(Rc::new(RefCell::new(TreeNode::new(6))));
    root.right.clone().unwrap().borrow_mut().right = Some(Rc::new(RefCell::new(TreeNode::new(7))));
    root.right.clone().unwrap().borrow_mut().right.clone().unwrap().borrow_mut().left = Some(Rc::new(RefCell::new(TreeNode::new(8))));
    let res = right_side_view(Some(Rc::new(RefCell::new(root))));
     println!("{:?}",res);
}

Complexity measures

Time complexity Space
...