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

Flatten Binary Tree to Linked List

Explore how to flatten a binary tree into a linked list using pre-order traversal in Rust. Understand step-by-step how to connect nodes, handle child pointers, and analyze the time and space complexity of the solution.

We'll cover the following...

Description

We are given the root of a binary tree. We have to flatten the tree into a linked list. The left child of the linked list is always null, and the right child points to the next node in the list. The nodes in the linked list should be in the same order as the pre-order traversal of the given binary tree.

Constraints

  • -100 <= 'Node.val' <= 100
  • The tree contains nodes in the range [0, 2000].

Let’s see how a flattened tree looks like in the illustration below:

Do it yourself

Rust 1.57.0
use std::rc::Rc;
use std::cell::RefCell;
#[derive(Debug, PartialEq, Eq, Clone)]
pub struct TreeNode {
  pub val: i32,
  pub left: Option<Rc<RefCell<TreeNode>>>,
  pub right: Option<Rc<RefCell<TreeNode>>>
}
impl TreeNode {
  pub fn new(val: i32) ->Self { 
    TreeNode {
      val,
      left: None,
      right: None
    }
  }
}

Solution

We will flatten the given binary tree into the linked list. We will keep the linked list in the pre-order traversal of the binary tree. We will be traversing the tree starting from the root.

Let’s see the following algorithm to implement the described problem.

  1. First, we will implement ...