Straighten the tree into a line
Rearrange a search tree into a chain in which each node has only a right child and the values increase, by relinking the nodes in inorder order. About 18 minutes.
Link in sorted order
A chain with each node having no left child and its right child being the next larger value is a sorted linked list in disguise. You can make it by reusing the nodes, without creating new ones.
Walk the tree in inorder order. Remember the last node linked, called the tail. Each visited node becomes the right child of the tail.
dummy = TreeNode(0) tail = dummy
- chain
- 3
The smallest value, 3, is visited first. It becomes the new root of the chain.
Clear the left side
Every node must end with no left child. Set the left link of each visited node to nothing. It is safe to do this at the visit, because the walk has already finished with the left subtree by then.
The first node visited is the smallest and becomes the new root, and there is no tail yet. The last node's right child must be nothing, which holds because that was already so for the largest node.
node.left = None # no left children
When is it safe to clear a node's left link?
- AWhen the node is visited, after its left subtree has been walked
- BBefore walking its left subtree
- CNever, the links are kept
Show the answer
When the node is visited, after its left subtree has been walked. The left subtree has been finished by then.
Increasing order search tree
Given the root of a binary search tree, rearrange the tree so that the leftmost node becomes the root, and every node has no left child and only one right child, the values increasing along the chain. Return the new root.
root = [5, 3, 6, 2, 4, null, 8, 1, null, null, null, 7, 9] → [1, null, 2, null, 3, null, 4, null, 5, null, 6, null, 7, null, 8, null, 9]
1 ≤ number of nodes ≤ 100 · 0 ≤ node.val ≤ 1,000