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

Flatten Binary Tree to Linked List

Understand how to convert a binary tree into a linked list that follows preorder traversal. This lesson guides you through an efficient algorithm that rearranges nodes in-place, using constant space and traversing each node once. You'll learn to manage node connections and implement this transformation in C++, building skills useful for coding interviews involving tree algorithms.

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:

Coding exercise

Files
main.cpp
TreeNode.h
C++ 17
TreeNode* flatten(TreeNode* root) {
    // write your code here
    return root;
}
Flatten binary tree to linked list

Solution

We will flatten the given binary tree into the linked list. We will keep the linked list in the pre-order ...