The challenge
Rewire the existing nodes into a preorder chain using right pointers, with every left pointer null.
Mutates the original tree. The root object and all node identities are preserved.
Example
Balanced example chain: 8 → 4 → 2 → 6 → 12 → 10 → 14.
Use the walkthrough below to inspect the input and each state change.
See Flatten tree, step by step
Follow the branches. Watch the state change.
View child pointers & node state
| Node | Value | Left | Right | State |
|---|---|---|---|---|
| A | 8 | B | C | — |
| B | 4 | D | E | — |
| C | 12 | F | G | — |
| D | 2 | null | null | — |
| E | 6 | null | null | — |
| F | 10 | null | null | — |
| G | 14 | null | null | — |
Inspect the input.
Labels identify node objects; numbers are their values. Left and right child pointers define the tree.
root = A:8View original input
A:8 [L:B, R:C] · B:4 [L:D, R:E] · C:12 [L:F, R:G] · D:2 [L:null, R:null] · E:6 [L:null, R:null] · F:10 [L:null, R:null] · G:14 [L:null, R:null]
Node IDs stay distinct even when values repeat. Pointer mutations update the diagram; removed nodes remain in the state table for reference.
Put it into code
Build the chain backward using reverse preorder: right, left, root.
Nodes store value, left, and right. C++ uses C++17 or later.
from collections import deque
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def flatten(root):
previous = None
def visit(node):
nonlocal previous
if node is None:
return
visit(node.right)
visit(node.left)
node.right = previous
node.left = None
previous = node
visit(root)
return root
#include <algorithm>
#include <cmath>
#include <functional>
#include <limits>
#include <map>
#include <optional>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
struct Node {
long long value;
Node *left = nullptr, *right = nullptr;
explicit Node(long long v) : value(v) {}
};
Node* flatten(Node* root) {
Node* previous = nullptr;
function<void(Node*)> visit = [&](Node* node) {
if (!node) return;
visit(node->right); visit(node->left);
node->right = previous;
node->left = nullptr;
previous = node;
};
visit(root);
return root;
}