# Binary Tree Construction From Mutliple Subtree

## 20 February 2022 - 1 answer

i have the following input like :

``````1:2:3 2:4:x 3:x:5
``````

which output like following binary tree:

``````root 1
and 2 3
4 x x 5
``````

is like the combination of all elements from the input to form a binary tree . any idea how to achieve this ? i have following code to implement the binary tree , but not sure how to convert this data structure into : root.left.left in order to insert

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

# A function to do inorder tree traversal
def printInorder(root):

if root:

# First recur on left child
printInorder(root.left)

# then print the data of node
print(root.val),

# now recur on right child
printInorder(root.right)

# A function to do postorder tree traversal
def printPostorder(root):

if root:

# First recur on left child
printPostorder(root.left)

# the recur on right child
printPostorder(root.right)

# now print the data of node
print(root.val),

# A function to do preorder tree traversal
def printPreorder(root):

if root:

# First print the data of node
print(root.val),

# Then recur on left child
printPreorder(root.left)

# Finally recur on right child
printPreorder(root.right)

# Driver code
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print "Preorder traversal of binary tree is"
printPreorder(root)
``````

I don't know if I understand: if you have problem to add new elements then you should write function which search `None` with some value - ie. `3` - and then it is not problem to add `found_node.right = 5`

``````def search(node, val):
if node.val == val:
return node

if node.left:
result = search(node.left, val)
if result:
return result

if node.right:
result = search(node.right, val)
if result:
return result

return None
``````

``````def add(root, data):
val, left, right = data.split(':')

found_node = search(root, int(val))

if found_node:
if left != 'x':
found_node.left  = Node(int(left))
if right != 'x':
found_node.right = Node(int(right))

# ---

root = Node(1)

``````

Minimal working code.

In `printPreorder` I added argument `position` to display `<` for left leaf, and `>` for right leaf.

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

# A function to do inorder tree traversal
def printInorder(root):

if root:

# First recur on left child
printInorder(root.left)

# then print the data of node
print(root.val),

# now recur on right child
printInorder(root.right)

# A function to do postorder tree traversal
def printPostorder(root):

if root:

# First recur on left child
printPostorder(root.left)

# the recur on right child
printPostorder(root.right)

# now print the data of node
print(root.val)

# A function to do preorder tree traversal
def printPreorder(root, position='!'):
if root:

# First print the data of node
if position == '<':
print(root.val, '<')
elif position == '>':
print('  >', root.val)
else:
print(' ', root.val, ' ')

# Then recur on left child
printPreorder(root.left, '<')

# Finally recur on right child
printPreorder(root.right, '>')

def search(node, val):
if node.val == val:
return node

if node.left:
result = search(node.left, val)
if result:
return result

if node.right:
result = search(node.right, val)
if result:
return result

return None

val, left, right = data.split(':')

found_node = search(root, int(val))

if found_node:
print('found_node:', found_node.val)
else:
print('found_node: None')

if found_node:
if left != 'x':
found_node.left = Node(int(left))
if right != 'x':
found_node.right = Node(int(right))

# Driver code
root = Node(1)

print('\n--- Preorder ---\n')
printPreorder(root)
``````

Result:

``````found_node: 1
found_node: 2
found_node: 3