Binary Tree Preorder Traversal

Write a program to find the  Binary Tree Preorder Traversal.

Example 1:

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

Example 2:

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

Approach 1: Recursion

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BinaryTreePreorderTraversalRecursion {
    public static void main(String[] args) {
        TreeNode tree = new TreeNode(1);
        tree.right = new TreeNode(2);
        tree.right.left = new TreeNode(3);
        preorder(tree);
        System.out.println("Tree Preorder is " + Arrays.asList(result));
    }

    static List<Integer> result = new ArrayList<>();

    public static void preorder(TreeNode root) {
        if (root == null)
            return;

        // Add root value
        result.add(root.val);
        // visit left node
        preorder(root.left);
        // visit right node
        preorder(root.right);

    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

// Time Complexity: O(n)

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data=data;
        this->left=NULL;
        this->right=NULL;
    }
};
//Function to find preorder Traversal
//of tree
void preorderTraversal(TreeNode *root)
{
    //Base Case
    if(root==NULL)
       return;
    //print root data
    cout<<root->data<<" ";
    //visit left subtree
    preorderTraversal(root->left);
    //visit right subtree
    preorderTraversal(root->right);
}
int main()
{
    TreeNode *tree=new TreeNode(1);
    tree->right=new TreeNode(2);
    tree->right->left=new TreeNode(3);
    cout<<"Preorder Traversal\n";
    preorderTraversal(tree);
    return 0;
}
//Time Complexity: O(n)

Approach 2: Iteration

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class BinaryTreePreorderTraversalIteration {
    public static void main(String[] args) {
        TreeNode tree = new TreeNode(1);
        tree.right = new TreeNode(2);
        tree.right.left = new TreeNode(3);
        preorder(tree);
        System.out.println("Tree Preorder is " + Arrays.asList(result));
    }

    static List<Integer> result = new ArrayList<>();
    static Stack<TreeNode> s = new Stack<>();

    public static List<Integer> preorder(TreeNode root) {
        if (root == null)
            return result;
        TreeNode c = root;
        while (c != null || !s.isEmpty()) {
            if (c != null) {
                result.add(c.val);
                s.push(c);
                c = c.left;
            } else {
                c = s.pop();
                c = c.right;
            }
        }
        return result;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

// Time Complexity: O(n)

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data=data;
        this->left=NULL;
        this->right=NULL;
    }
};
//Function to find preorder Traversal
//of tree
vector<int> preorderTraversal(TreeNode *root)
{
    vector<int> res;
    stack<TreeNode*> st;
    TreeNode *temp=root;
    while(temp!=NULL||!st.empty())
      {
          if(temp!=NULL)
            {
                res.push_back(temp->data);
                st.push(temp);
                temp=temp->left;
            }
          else
          {
              temp=st.top();
              st.pop();
              temp=temp->right;
          }
          
      }
      return res;
}
int main()
{
    TreeNode *tree=new TreeNode(1);
    tree->right=new TreeNode(2);
    tree->right->left=new TreeNode(3);
    cout<<"Preorder Traversal\n";
    vector<int> res=preorderTraversal(tree);
    int n=res.size();
    for(int i=0;i<n;i++)
       cout<<res[i]<<" ";
    
    return 0;
}
//Time Complexity: O(n)