Complete the preorder function. It must print the values in the tree's preorder traversal as a single line of space-separated values.

Input Format

Our hidden tester code passes the root node of a binary tree to your_preOrder_function.

Constraints

Nodes in the tree

Output Format

Print the tree's preorder traversal as a single line of space-separated values.

Sample Input

     1
      \
       2
        \
         5
        /  \
       3    6
        \
         4

Sample Output

1 2 5 3 4 6

Code:

def pre_order_traversal(root,result):
    if not root:
        return

    stack = []
    stack.append(root)

    while stack:
        node = stack.pop()
        result.append(node.data)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)