Leetcode – Increasing Order Search Tree Solution in Python

Spread the love

The Increasing Order Search Tree problem is an intriguing binary tree problem available on Leetcode. It evaluates one’s understanding of tree traversal, manipulation, and reconstruction. In this in-depth article, we’ll unpack the problem statement, walk through different approaches, present Python solutions, and finally, analyze their time and space complexities.

Table of Contents:

  1. Understanding the Problem Statement
  2. Basic Tree Traversal Concepts
  3. Initial Approach: Using Inorder Traversal
  4. Optimized Approach
  5. Python Implementations
  6. Complexity Analysis
  7. Conclusion

1. Understanding the Problem Statement

Problem:

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.

Example:

Given the root of the following tree:

    5
   / \
  3   6
 / \   \
2   4   8
       / \
      7   9

Your output should be:

2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

2. Basic Tree Traversal Concepts

The problem is rooted in the concept of Inorder Traversal of binary trees, which gives nodes in non-decreasing order for a Binary Search Tree (BST). This traversal follows the pattern: left subtree -> current node -> right subtree.

3. Initial Approach: Using Inorder Traversal

Start with an inorder traversal and store each node’s value in a list. Then, construct a new tree from the sorted list, where each node only has a right child.

Steps:

  1. Perform an inorder traversal and store node values in a list.
  2. Initialize a new tree with a temporary root.
  3. Iterate over the list, creating new nodes as right children.

4. Optimized Approach

Rather than using additional space like a list, we can manipulate the tree during the traversal process itself.

Steps:

  1. Initialize a new tree with a temporary root.
  2. Perform a modified inorder traversal:
    • Traverse the left subtree.
    • Update the tree, attaching the current node as a right child.
    • Traverse the right subtree.

5. Python Implementations

Initial Approach:

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

def increasingBST(root):
    def inorder(node):
        return inorder(node.left) + [node.val] + inorder(node.right) if node else []

    vals = inorder(root)
    ans = cur = TreeNode(None)
    for v in vals:
        cur.right = TreeNode(v)
        cur = cur.right
    return ans.right

Optimized Approach:

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

def increasingBST(root):
    def inorder(node):
        nonlocal cur
        if node:
            inorder(node.left)
            node.left = None
            cur.right = node
            cur = node
            inorder(node.right)

    ans = TreeNode(None)
    cur = ans
    inorder(root)
    return ans.right

6. Complexity Analysis

Initial Approach:

Time Complexity: O(n) – We need to traverse each node once.

Space Complexity: O(n) – We store the values of all nodes in a list.

Optimized Approach:

Time Complexity: O(n) – Each node is processed once.

Space Complexity: O(h) – The height of the tree represents the maximum number of recursive calls on the call stack. In the worst case, a skewed tree, this will be O(n), but for a balanced tree, it will be O(log⁡n).

7. Conclusion

The Increasing Order Search Tree problem on LeetCode encapsulates fundamental tree traversal and manipulation techniques. While the initial approach offers simplicity, the optimized approach shines with its efficiency and clever in-place transformation.

Leave a Reply