Vultr DocsLatest Content

Increasing Order Search Tree

Updated on 03 June, 2025
Increasing Order Search Tree header image

Problem Statement

The task is to modify a binary search tree (BST) by rearranging its nodes so it forms a right-skewed tree. Each node in this modified tree should have no left child and only one right child, starting from the leftmost node of the original BST. This transformation requires a traversal of the nodes in their in-order sequence to recreate the tree appropriately, ensuring that the smallest node becomes the root and leading upwards sequentially.

Examples

Example 1

Input:

root = [5,3,6,2,4,null,8,1,null,null,null,7,9]

Output:

[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

Example 2

Input:

root = [5,1,7]

Output:

[1,null,5,null,7]

Constraints

  • The number of nodes in the given tree will be in the range [1, 100].
  • 0 <= Node.val <= 1000

Approach and Intuition

The key to solving this problem lies in understanding the properties of the BST and the in-order traversal method:

  1. First, perform an in-order traversal of the BST. This traversal will access the nodes in ascending order due to the properties of the BST where:

    • Left subtree nodes < Root
    • Right subtree nodes > Root

  2. During the traversal, store the nodes in a temporary list as they appear.

  3. Once all nodes are accessed and stored, reconstruct the BST from this list:

    • Take the first element in the list as the root.
    • Iterate through the rest and for each node, set it as the right child of the previous node so that no left children exist.

This streamlined approach leverages the in-order traversal which naturally aligns with the requirement of creating a singly-linked right-skewed "tree", which visually will resemble a linked list more than a traditional binary tree.

Solutions

  • Java
  • Python
java 
class Solution {    
    public TreeNode rearrangeTree(TreeNode root) {
        List<Integer> values = new ArrayList();
        collectInOrder(root, values);
        TreeNode newRoot = new TreeNode(0), current = newRoot;
        for (int value: values) {
            current.right = new TreeNode(value);
            current = current.right;
        }
        return newRoot.right;
    }

    public void collectInOrder(TreeNode node, List<Integer> values) {
        if (node == null) return;
        collectInOrder(node.left, values);
        values.add(node.val);
        collectInOrder(node.right, values);
    }
}

This Java solution focuses on transforming a binary search tree into an increasing order search tree where all nodes are rearranged to follow a strictly increasing order with all nodes on the right subtree and none on the left. The process includes:

  • Creating a helper method collectInOrder to traverse the original tree in an in-order manner. This method collects values from the tree and stores them in a list which ensures they are in ascending order.

  • In the rearrangeTree method:

    • Initialize a temporary dummy node. This helps in easily constructing the new tree without handling special case for the root.
    • Iterate through the collected values, creating new nodes to the right of the current node. This step builds the right-skewed tree by attaching each new node to the right of the last node.

  • Finally, the method returns the right child of the dummy node which is the root of the newly formed increasing order search tree.

Ensure the initial input tree is a valid binary search tree to maintain the order correctly in the output tree.

python 
class Solution:
    def increasingBST(self, root):
        def in_order_traversal(current_node):
            if current_node:
                yield from in_order_traversal(current_node.left)
                yield current_node.val
                yield from in_order_traversal(current_node.right)

        result_tree = current = TreeNode(None)
        for value in in_order_traversal(root):
            current.right = TreeNode(value)
            current = current.right
        return result_tree.right

This solution addresses the challenge of restructuring a binary search tree (BST) into a new tree that maintains the original BST's values in increasing order, where the new tree has only right children nodes, effectively forming a linked list.

  • Start by defining the increasingBST function which initially declares an inner generator function named in_order_traversal. This inner function performs a classic in-order traversal of the binary tree.
  • Utilize a generator yield to output the node's value during the traversal. This strategy efficiently processes the tree without needing additional data structures to store intermediate results.
  • In the increasingBST function, initiate result_tree with a TreeNode set to None. This serves as a temporary dummy node to facilitate easier tree assembly.
  • Iterate through all values generated by in_order_traversal:
    • For each value, append a new node with this value to the 'right' of the current tree.
    • Update the current pointer to point to the newly created node.
  • The function returns result_tree.right, effectively omitting the initial dummy node and returning the head of the newly formed right-skewed tree.

This approach ensures that the tree remains compact and the linkage is efficiently handled within the constraints of the given BST values, using minimal space overhead and maintaining an optimal runtime complexity characteristic of in-order traversal.

Comments

No comments yet.