Binary Tree Pre-Order Traversal

This article is another part of a series on leet code problems solutions, and it provides a solution to the leet code problem number 102. This is a Leet code problem named Binary Tree Pre Order Traversal. We will solve it using python and it is the best space and time-optimized solution.

Question of Binary Tree Pre Order Traversal

Given the root of a binary tree, return the preorder traversal of its nodes’ values.

In Pre Order Traversal we simply traverse in the NLR format. That is in NLR format we first read node then left side of node than right side of the node.

Example

Example 1

Input: root = [1,null,2,3]
Output: [1,2,3]

Example 2

Input: root = []
Output: []

Example 3

Input: root = [1]
Output: [1]

Constraints

The number of nodes in the tree is in the range [0, 2000].
-1000 <= Node.val <= 1000

Approach to solve Binary Tree Pre Order Traversal

To solve this problem we will first visit through the root node after that we visit the left node and at last, we visit the right node in a recursive manner.

Algorithm

This method performs the following steps for a given input array:

Create nodes array to store nodes.
Create an inner function to do recursion.
Check if the root exists. If yes then go to step 4 otherwise break inner function.
append the value of root to node variable.
Call left child of root recursively.
Call right child of root recursively.
End if
End inner function
return node

Python Code for Binary Tree Pre Order Traversal

# 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
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        
         # arr to store nodes
        nodes = []
        
        #use inner function to save space and time 
        def helper(root, arr): 
            # if there is root to traverse
            if root: 
                #append the root node
                arr.append(root.val)
                #check for left child
                helper(root.left,arr)
                #check for right child
                helper(root.right,arr)
                
        #calling the inner function
        helper(root,nodes)

        return nodes