Preorder Traversal

Problem

Given a binary tree, find its preorder traversal.

Examples:

Example 1:

Input:
        1      
      /          
    4    
  /    \   
4       2
Output: 1 4 4 2 

Example 2:

Input:
       6
     /   \
    3     2
     \   / 
      1 2
Output: 6 3 1 2 2 

Your task:

You just have to complete the function preorder() which takes the root node of the tree as input and returns an array containing the preorder traversal of the tree.

• Expected Time Complexity: $O(N)$
• Expected Auxiliary Space: $O(N)$

Constraints:

• $1 <=$ Number of nodes $<= 10^4$
• $0 <=$ Data of a node $<= 10^5$

Solution

Python

def preorder(root):
    arr = []
    def traverse(node):
        if node is None:
            return
        arr.append(node.data)
        traverse(node.left)
        traverse(node.right)
    traverse(root)
    return arr

Java

static ArrayList<Integer> preorder(Node root) {
    ArrayList<Integer> arr = new ArrayList<>();
    traverse(root, arr);
    return arr;
}

static void traverse(Node node, ArrayList<Integer> arr) {
    if (node == null)
        return;
    arr.add(node.data);
    traverse(node.left, arr);
    traverse(node.right, arr);
}

C++

void traverse(Node* node, std::vector<int>& result);

vector<int> preorder(Node* root) {
    vector<int> result;
    traverse(root, result);
    return result;
}

void traverse(Node* node, vector<int>& result) {
    if (node == nullptr)
        return;
    result.push_back(node->data);
    traverse(node->left, result);
    traverse(node->right, result);
}

• Time Complexity: $O(N)$
• Auxiliary Space: $O(N)$