In this tutorial, i am going to discuss what is binary tree preorder traversal? How to implement binary tree preorder traversal with and without recursion.
Given the root of a binary tree, write a code to return the preorder traversal of its nodes’ values.
What is preorder traversal?
In preorder traversal –
i) First, we visit the root.
ii) Traverse the left subtree of root in preorder.
iii) Traverse the right subtree of root in preorder.
Binary tree inorder traversal without using recursion
Binary tree level order traversal
Binary Tree Preorder Traversal without Recursion – Java Code
To implement preorder traversal using iterative approach, we are going to use stack data structure. Here are the implementation steps –
i) Declare an stack and push the root node in a stack.
ii) Run a loop while stack is not empty and do the following steps.
a) Pop an item from a stack and add it’s value in a result list.
b) Push the right child of popped item to stack, if it’s not empty.
c) Push the left child of popped item to stack, if it’s not empty.
We have to push the right child before the left child in a stack to make sure that the left subtree is processed first.
The time complexity of this approach is O(n) and its space complexity is also O(n).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
//Preorder traversal without using recursion public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if(root == null) { return result; } Stack<TreeNode> st = new Stack<>(); st.push(root); while(!st.isEmpty()) { TreeNode temp = st.pop(); result.add(temp.val); if(temp.right != null) { st.push(temp.right); } if(temp.left != null) { st.push(temp.left); } } return result; } |
Binary Tree Preorder Traversal using Recursion – Java Code
The recursive code is very straightforward. Here is the implementation.
i) Add the node value to a result list.
ii) Recursively call preorderHelper for the left node
iii) Recursively call preorderHelper for the right node
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
//Recursive implementation of preorder traversal class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if(root == null) { return result; } preorderHelper(root, result); return result; } public void preorderHelper(TreeNode root, List<Integer> result) { if(root == null) { return; } result.add(root.val); preorderHelper(root.left, result); preorderHelper(root.right, result); } } |
