Search Tree Into a Line

Easy

You are given the root of a binary search tree: in the left subtree of any node every value is smaller than the node's value, and in the right subtree every value is larger. Rebuild the tree into a "line": the node with the smallest value becomes the root, no node has a left child, and each node's right child is the node with the next larger value. Return the new root.

Example 1

root=tree_node([20, 10, 30, None, 15]) → [10, None, 15, None, 20, None, 30]

In increasing order the values are 10, 15, 20, 30. The new root is 10, and every node has only a right child.

Example 2

root=tree_node([4, 2, 6, 1, 3, 5, 7]) → [1, None, 2, None, 3, None, 4, None, 5, None, 6, None, 7]

A full tree of seven nodes is stretched into the chain 1 → 2 → … → 7.

Example 3

root=tree_node([42]) → [42]

A single node is already a chain.

Constraints

1 ≤ number of nodes ≤ 100
0 ≤ Node.val ≤ 1000
The tree is a binary search tree with distinct values

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack Tree Depth-First Search Binary Search Tree Binary Tree

Similar problems

K Keys Nearest to a Target Hard Pair Across Two Search Trees Medium Left, Node, Right Easy Parent Before Children Easy Children Before Parent Easy

Input

root=tree_node([20, 10, 30, None, 15])

Expected

[10, None, 15, None, 20, None, 30]

Run checks the first 3 tests in your browser. Submit checks all 27 tests on the server, hidden ones included.