Binary Tree Preorder Traversal - The Coding Shala

Last Updated: 19-Jan-2021
Home >> Data Structures >> Binary Tree Preorder Traversal

 In this post, we will learn how to Traverse a Binary Tree in Pre-Order.

Binary Tree Preorder Traversal

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

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3
Output: [1,2,3]

Preorder Traversal of Binary Tree in Java

Approach 1

Using Recursion.

Java Program: 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> Pre_Order = new ArrayList<Integer>();
        if(root == null) return Pre_Order;
        Pre_Order.add(root.val);
        Pre_Order.addAll(preorderTraversal(root.left));
        Pre_Order.addAll(preorderTraversal(root.right));
        return Pre_Order;
    }
}

Approach 2

Iterative solution. Using Stack[DFS].

Java Program: 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<Integer>();
        if(root == null) return ans;
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while(!stack.empty()){
            TreeNode curr = stack.pop();
            ans.add(curr.val);
            if(curr.right != null) stack.push(curr.right);
            if(curr.left != null) stack.push(curr.left);
        }
        return ans;
    }
}


Other Posts You May Like
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Java Program to Convert Binary to Decimal - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

N-th Tribonacci Number Solution - The Coding Shala

Introduction to Kotlin Programming Language for Backend Development - The Coding Shala

Java Program to Reverse a String using Stack - The Coding Shala