Binary Tree Construction From Mutliple Subtree

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

and adding new elements

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)

add(root, '1:2:3')
add(root, '2:4:x')
add(root, '3:x:5')

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

def add(root, data):
    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':
            print('- add left :', left)
            found_node.left = Node(int(left))
        if right != 'x':
            print('- add right:', right)
            found_node.right = Node(int(right))
    
# Driver code
root = Node(1)

add(root, '1:2:3')
add(root, '2:4:x')
add(root, '3:x:5')

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

Result:

found_node: 1
- add left : 2
- add right: 3
found_node: 2
- add left : 4
found_node: 3
- add right: 5

--- Preorder ---

  1  
2 <
4 <
  > 3
  > 5