897. Increasing Order Search Tree
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 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
Source
In [1]:
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
Code
In [2]:
def increasing_bst(root):
"""Using recursive (reverse) inorder (DFS) traversal with a stack
Time Complexity: O(n)
Space Complexity: O(n)
"""
def inorder_reverse(node):
# base case
if node is None:
return
# return list of nodes in reverse order
nonlocal nodes
inorder_reverse(node.right)
nodes.append(node)
inorder_reverse(node.left)
if not root:
return None
nodes = []
inorder_reverse(root) # now nodes = [n0, n1, ... nm] with n0 > n1 > ... > nm
head = nodes.pop()
parent = head
while nodes:
child = nodes.pop() # [n0, n1, ..., ni] <-- nj (child) nk (parent) <-- nl
child.left, child.right = None, None # [n0, n1, ..., ni] nj (child) nk (parent) <-- nl
parent.left, parent.right = None, child # [n0, n1, ..., ni] nj (child) <-- nk (parent) <-- nl
parent = child # [n0, n1, ..., ni] nj (parent) <-- nk <-- nl
return head
In [3]:
def increasing_bst(root):
"""Alternative version of first solution (inorder + no popping elements)
Time Complexity: O(n)
Space Complexity: O(n)
"""
def inorder(node):
# base case
if not node:
return
# return list of nodes in reverse order
nonlocal nodes
inorder(node.left)
nodes.append(node)
inorder(node.right)
if not root:
return None
nodes = []
inorder(root) # now nodes = [n0, n1, ... nm] with n0 < n1 < ... < nm
for i, n in enumerate(nodes[:-1]):
n.left, n.right = None, nodes[i+1]
nodes[-1].left, nodes[-1].right = None, None
return nodes[0]
In [ ]:
# Same as first solution but using deque instead of stack (avoids reverse traversal)
from collections import deque
def increasing_bst(root):
"""Using recursive inorder (DFS) traversal with a deque
Time Complexity: O(n)
Space Complexity: O(n)
"""
def inorder(node):
# base case
if node is None:
return
# return list of nodes in (normal) order
nonlocal nodes
inorder(node.left)
nodes.append(node)
inorder(node.right)
if not root:
return None
nodes = deque()
inorder(root) # now nodes = [n0, n1, ... nm] with n0 < n1 < ... < nm
head = nodes.popleft() # deque !
parent = head
while nodes:
child = nodes.popleft() # deque ! # --> ni (parent) nj (child) --> [nk, nl, ..., nm]
child.left, child.right = None, None # --> ni (parent) nj (child) [nk, nl, ..., nm]
parent.left, parent.right = None, child # --> ni (parent) --> nj (child) [nk, nl, ..., nm]
parent = child # --> ni --> nj (parent) [nk, nl, ..., nm]
return head
Follow up #1:
Solve it both recursively and iteratively.
Code
In [4]:
def increasing_bst(root):
"""inorder (DFS) with iterative traversal
Time Complexity: O(n)
Space Complexity: O(n)
"""
if not root:
return None
stack = []
nodes = []
n = root
while n or stack:
while n: # go to the leftmost child
stack.append(n)
n = n.left
# if no more left child, get the 1st right node and check for leftmost child again
n = stack.pop()
nodes.append(n)
n = n.right
for i, n in enumerate(nodes[:-1]):
n.left, n.right = None, nodes[i+1]
nodes[-1].left, nodes[-1].right = None, None
return nodes[0]
Follow up #2:
Solve it with O(1) memory.
Code
In [ ]:
def increasing_bst(root):
"""Inorder recursive approach with O(1) memory, using a generator."""
def inorder(node):
if not node:
return None
yield from inorder(node.left)
yield node
yield from inorder(node.right)
parent = head = TreeNode(None)
for node in inorder(root):
node.left = None # avoid cycles
parent.right = node
parent = node
return head.right
In [ ]:
def increasing_bst(root):
"""Same as above but more subtle (see below for explanations)."""
def inorder(node, parent):
# base case
if not node:
return parent
head = inorder(node.left, node) # find the leftmost node
node.left = None # avoid cycles
node.right = inorder(node.right, parent)
return head
return inorder(root, None)
In [ ]:
# n3 n3
# (node) (*parent*)
# / \ / \
# n0 n5 n0 n5
# \ / \ ==> (*node*) / \ ==>
# n2 n4 n6 \ n4 n6
# / n2
# n1 /
# n1
#
#
#
# n3 n3
# (*parent*)
# / \ / \
# n0 n5 n0 n5
# (*parent*) / \ ==> (*node*) / \ ==>
# / \ n4 n6 (*head*) n4 n6
# . n2 \
#(*node*) / n2
# n1 /
# n1
#
#
#
# n3 n3
# (*parent*)
# / \ / \
# n0 n5 n0 n5
# (*head*) / \ ==> \ / \ ==>
# \ n4 n6 n2 n4 n6
# n2 (*parent*)
# (*node*) /
# / n1
# n1 (*node*)
# (*head*)
#
#
#
# n3 n3
# (*parent*)
# / \ / \
# n0 n5 n0 n5
# \ / \ ==> \ / \ ==>
# n2 n4 n6 n1 n4 n6
# (*parent*) (*head*)
# / \^ \
# n1 \^ n2
# (*node*) \^ (*node*)
# (*head*) \^
# v\______\^
# > > > > ^
#
#
#
# n3 n0 n0
# (*parent*) \ (*head*)
# / \^ \ n1 \
# n0 \^ n5 (*head*) n1
# \ \^ / \ \ \
# n1 \^ n4 n6 ==> n2 ==> n2
# (*head*) \^ (*node*) \
# \ \^ \ n3
# n2 \^ n3 (*node*)
# (*node*) \^ (*parent*) \
# v\________\^ \ n5
# > > > > > > ^ n5 / \
# / \ n4 n6
# n4 n6
#