Binary Tree Preorder Traversal Iterative, Recursive

Being a Software Engineer you would have always been asked in most of the interviews to tell about Binary Tree Preorder traversal algorithm in Iterative and Recursive form. You can also find these questions on Leetcode.com and Interviewbit website.

Since the Recursive method of Binary Tree Preorder is very easy. It becomes a little tedious and lengthy code for the iterative version in which we need to use a while loop and stack or queue to solve the problem.

Question: PreOrder Traversal LeetCode and InterviewBit

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

Solution: Algorithm (Iterative)

To solve this problem in the Iterative case. All we need to do is use a stack to store the current root node information. And once you pop or retrieve a node from the stack, then we pop that node and store any node available to the right in the stack and available to left in the stack.

• Initialize a list to store the preorder traversal.
• Initialize the empty stack and store root of the binary tree.
• Start a loop until the stack is found empty.
• store the top element of the stack in temp variable and then using pop remove that top element in stack.
• Push the temp which is top of the stack in the list.
• Push the right node of temp which is top of the stack in the current stack.
• Push the left node of temp which is top of the stack in the current stack.
• Once stack becomes empty, Then return the list which contains the preorder traversal.

C++ Code for Iterative Solution

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root==NULL) return res;
        stack<TreeNode*> preOrd;
        preOrd.push(root);
        while(!preOrd.empty()){
            TreeNode* tmp = preOrd.top();
            preOrd.pop();
            res.push_back(tmp->val);
            if(tmp->right!=NULL) preOrd.push(tmp->right);
            if(tmp->left!=NULL) preOrd.push(tmp->left);
        }
        return res;
    }
};

JAVA Solution for Iterative Version:

/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new LinkedList<>();
    Deque<TreeNode> stack = new LinkedList<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if (node != null) {
            result.add(node.val);
            stack.push(node.right);
            stack.push(node.left);
        }
    }
    return result;
}

Python Iterative Solution

# 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: TreeNode) -> List[int]:
        newStack, returnNewRoot = [root], []
        while newStack:
            getNode = newStack.pop()
            if getNode:
                returnNewRoot.append(getNode.val)
                newStack.append(getNode.right)
                newStack.append(getNode.left)
        return returnNewRoot

Recursive Solution for PreOreder Traversal in C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void getPreOrder(TreeNode* root, vector<int> &res){
        if(root==NULL) return;
        res.push_back(root->val);
        getPreOrder(root->left, res);
        getPreOrder(root->right, res);
        return ;
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root==NULL) return res;
        getPreOrder(root, res);
        return res;
    }
};

If you liked the answer then please follow us on Facebook and Twitter. Let us know the questions and answer you want to cover in this blog.

Wanna read more interview-related questions? Check Top Interview Questions category.