Abstract / Summary

Given a binary search tree rearrange its nodes so they form a single right leaning chain in increasing order

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 79% (400k+ submissions).

Typical patterns to solve this problem:

• Binary Search Tree
• Binary Tree
• Depth First Search
• Stack
• Tree

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation transforms a binary search tree (BST) into a right-leaning “increasing” tree where every node has no left child and its right child points to the next larger value. The algorithm follows a classic in-order traversal to collect nodes in sorted order, then rewires the pointers to produce the desired structure. The code is concise, leverages recursion for depth-first traversal, and performs the re-linking in a single pass over the collected nodes.

Key Steps

The solution can be divided into two conceptual phases: gathering the nodes in sorted order and rebuilding the tree with the required shape.

In-order Traversal and Collection

A helper function deeper recursively visits the left subtree, records the current node, and then visits the right subtree. This order guarantees that nodes are appended to the list all in ascending key order for a BST.

def deeper(node):
    if node:
        deeper(node.left)
        all.append(node)
        deeper(node.right)

The outer call deeper(root) initiates the traversal from the root of the original tree. The list all ends up containing references to the original node objects, preserving their values while discarding the original structural relationships.

Re-linking Nodes into a Right-Skewed Tree

After the traversal, a simple loop iterates over the list all. For each node, the left child is cleared, and the right child is set to the next node in the list, except for the final node which retains a None right pointer.

for i in range(len(all)):
    all[i].left = None
    if i < len(all) - 1:
        all[i].right = all[i + 1]

The loop directly mutates the original node objects, avoiding the creation of new nodes. The first element of all becomes the new root of the transformed tree, which is returned to the caller.

Edge Cases Handled

The algorithm gracefully handles an empty input tree. When root is None, the recursive deeper function never appends any element to all. The subsequent loop does not execute because the length of all is zero, and the final return statement attempts to access all[0]. In this particular implementation, the assumption is that the input tree is non-empty, which aligns with typical problem constraints where a BST is guaranteed to contain at least one node. Therefore, the code implicitly expects a valid tree and correctly processes the minimal case of a single-node tree: the traversal adds that node to all, the loop clears its left child (already None) and leaves its right child as None, and the node is returned as the new root.

Performance Optimizations

The solution achieves efficiency by reusing the original node objects rather than allocating new ones. This in-place modification reduces memory overhead and eliminates the need for additional data structures beyond the list that stores references. The traversal visits each node exactly once, and the re-linking loop also touches each node a single time, resulting in a linear pass over the tree. By performing the pointer adjustments after the full collection, the algorithm avoids repeated modifications during recursion, which could otherwise lead to unnecessary intermediate state changes. The use of a simple Python list for storage provides O(1) amortized append operations, ensuring that the collection phase remains fast even for large trees.

Imagine a big tree made of wooden blocks. Each block has a letter or a number on it, and the blocks are connected in a messy way that branches out in many directions. This code wants to take all those blocks and line them up in a perfectly straight row, just like a train on a track.

First, it goes on a treasure hunt through the tree. It starts at the top and keeps moving left as far as it can until it finds a block. Once it finds one, it puts that block into a long, empty line and then checks to see if there is another block to the right. It keeps doing this until every single block from the tree is sitting in that long line in the right order.

After all the blocks are gathered in the line, the code does a bit of tidying up. It walks down the line and tells every block to let go of any other pieces attached to its left side, because a straight train does not need any side pieces. Then, it connects each block to the one right behind it on the right side. By the time it finishes, all the blocks that were once scattered in a messy tree are now standing in a simple, straight line, pointing toward the right.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java						TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java				Go		TS
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai				Java
	DimitrisJim									C
	everthis			JS
	fartem							Ruby
	fpdjsns	C++
	halfrost								Go
	JoshCrozier			JS
	keineahnung2345	C++
	Krazune	C++
	lkwq007		Python
	ruoru						Rust
	suxrobGM					C#
	varunu28				Java
	wisdompeak	C++
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fpdjsns	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lkwq007	Python
ruoru	Rust
suxrobGM	C#
varunu28	Java
wisdompeak	C++
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality