# Reconstruct Binary Search Tree from Binary Tree

• Given a Binary Tree each node of which contains an integer, reconstruct a Binary Search Tree from the integers of the input Binary Tree, the reconstructed Binary Search Tree should be in the same shape as the input Binary Tree.

``````class Node:
"""docstring for Node"""
def __init__(self, val = None):
self.val = val
self.left = None
self.right = None

def dfs(root, res, size):
if root == None:
return 0
else:
res.append(root.val)
lsize = dfs(root.left, res, size)
rsize = dfs(root.right, res, size)
size[root] = (lsize, rsize)
return 1 + lsize + rsize

def construct(nums, root, size):
lsize, rsize = size[root]
newRoot = Node(nums[lsize])
if lsize != 0:
newRoot.left = construct(nums[:lsize], root.left, size)
if rsize != 0:
newRoot.right = construct(nums[lsize + 1:], root.right, size)
return newRoot

def convert(root):
res = []
size = {}
dfs(root, res, size)
res.sort()
return construct(res, root, size)

root = Node(1)
root.right = Node(0)
# root.left = Node(2)
newRoot = convert(root)
print(newRoot.val, newRoot.left.val if newRoot.left else None, newRoot.right.val if newRoot.right else None)

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.