Rustle up Your LeetCode Skills [1/N]: Maximum Depth of Binary Tree

Rust, the internet’s latest dearest, was developed by Mozilla Research, and first released in 2010. Rust is a modern systems programming language focused on safety, concurrency, and performance. It gained popularity for its ability to prevent common programming errors such as null pointer dereferences and data races.

Rust is rapidly gaining ground as a new tool in data and machine learning engineering. Rust’s low-level control, seamless integration with other languages, and strong safety guarantees make Rust valuable for building high-performance data processing systems and optimizing machine learning models.

Let’s stay ahead of the curve, and deep into rust syntax by solving some Leetcode problem!

Join me in my journey to unravel the mysteries of this language.

Today, we solve Maximum Depth of Binary Tree.

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

For example, looking at the example below,

We see that the tree has three levels, as the root split into two nodes and the left node splits further into two final nodes.

The easiest way to solve this problem when we are given the root is to explore each level one at a time. By this, we mean that we add children of nodes of the same level to a stack until we have explored all nodes on the same level, then repeat until we cannot proceed to a new level. Then we have reached the final level, i.e. max depth.

First, we need to define a data structure for a tree,

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
  pub val: i32,
  pub left: Option<Rc<RefCell<TreeNode>>>,
  pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
  #[inline]
  pub fn new(val: i32) -> Self {
    TreeNode {
      val,
      left: None,
      right: None
    }
  }
}

For the sake of this round, let us not worry too much about std::rc::Rc and std::cell:RefCell. The only thing, we need to care for now is that in order to be able to get the children from a node op type Rc<RefCell<TreeNode>>`, we need to “borrow” the wrapped value.

As discussed, in our solution we need a number of ingredients.

First, on each level we need to collect children into stack.

let mut level_stack = vec![];

Since we are updating the stack, we need to make it mutable, with let mut . As we pop the parents from the stack, we extract the non-null children and add to stack.

if parent.left.clone().is_some()  {
   level_stack.push(left);
}
if parent.right.clone().is_some() {
   level_stack.push(right);
}

Syntactically, we can even rewrite this as,

if let Some(left) = parent.left.clone()  {
  level_stack.push(left);
}
if let Some(right) = parent.right.clone() {
   level_stack.push(right);
}

What remain now is to pop each parents from the stack, so we can extract children,

for node in stack {
   let parent = node.borrow();
    -- extract children and add to level_stack
}
stack = level_stack;

We can now combine everything into the final code,

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
  pub val: i32,
  pub left: Option<Rc<RefCell<TreeNode>>>,
  pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
  #[inline]
  pub fn new(val: i32) -> Self {
    TreeNode {
      val,
      left: None,
      right: None
    }
  }
}
use std::rc::Rc;
use std::cell::RefCell;

struct Solution;
impl Solution {
    pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        if let Some(root) = root {
        let mut stack = vec![];
        let mut max_depth = 0;

        stack.push(root);

        while !stack.is_empty() {
            max_depth += 1;
            let mut level_stack = vec![];

            for node in stack {
                
                let parent = node.borrow();

                if let Some(left) = parent.left.clone()  {
                    level_stack.push(left);
                }
                if let Some(right) = parent.right.clone() {
                    level_stack.push(right);
                }
            
            }
            stack = level_stack;
        }

        return max_depth;
    }
    return 0;
    }
}

Feel free to check with the following unit test

#[cfg(test)]
mod tests {
    #[test]
    fn test_case_0() {
        use crate::max_depth::Solution;
        use crate::max_depth::TreeNode;
        use std::rc::Rc;
        use std::cell::RefCell;

        let mut root = TreeNode::new(3);
        let mut left = TreeNode::new(9);
        let mut right = TreeNode::new(20);
        let right_left = TreeNode::new(15);
        let right_right = TreeNode::new(7);

        right.left = Some(Rc::new(RefCell::new(right_left)));
        right.right = Some(Rc::new(RefCell::new(right_right)));

        left.left = None;
        left.right = None;

        root.left = Some(Rc::new(RefCell::new(left)));
        root.right = Some(Rc::new(RefCell::new(right)));

        assert_eq!(Solution::max_depth(Some(Rc::new(RefCell::new(root)))), 3);
    }
}

What did we learn today?

• we created a stack, pushed and popped from stack
• how to manipulate mutable variables
• how to implement breadth-first search from tree

What do we need to understand better?

I did not explain what “borrow” meant, but this is only the start. See you in the next one!

Feed back welcome and …