We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Increasing Order Search Tree

Difficulty: Easy

Problem Description

Given the root of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.

Key Insights

  • The problem involves transforming a binary search tree (BST) into a linear tree structure.
  • In-order traversal of a BST produces nodes in sorted order.
  • We can utilize a stack or recursion to perform in-order traversal.
  • The final structure should only have right children, maintaining the sorted order.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of nodes in the tree, as we visit each node once. Space Complexity: O(h) - where h is the height of the tree, due to the recursion stack or the stack used for in-order traversal.

Solution

To solve the problem, we can perform an in-order traversal of the binary search tree. During this traversal, we can build a new tree where each node only has a right child. We can use a current pointer to keep track of the last added node, ensuring we link the nodes correctly. This approach effectively flattens the tree into a linked-list-like structure.

Code Solutions

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def increasingBST(root: TreeNode) -> TreeNode:
    def in_order(node: TreeNode):
        if not node:
            return
        in_order(node.left)  # Traverse left
        node.left = None     # Set left child to None
        self.current.right = node  # Link the current node
        self.current = node   # Move current to this node
        in_order(node.right)  # Traverse right

    dummy = TreeNode(0)      # Dummy node to facilitate the process
    self.current = dummy      # Keep track of the last node added
    in_order(root)           # Start in-order traversal
    return dummy.right       # Return the right child of the dummy node
← Back to All Questions