Preorder Traversal

Intuition

Preorder traversal is one of the depth-first traversal methods used to explore nodes in a binary tree. The algorithm first visits the root node, then in the preorder traversal, we visit (i.e., add to the array) the current node by accessing its value, then we recursively traverse the left subtree in the same manner. We repeat these steps for the left subtree, then when we return to the current node, we recursively travel to the right subtree in a preorder manner as well. The sequence of steps in preorder traversal follows: Root, Left, Right.

Approach

Base Case: If the current node is null, it means we have reached the end of a subtree and there are no further nodes to explore. Hence the recursive function stops and we return from that particular recursive call.
Recursive Function:
- Process Current Node: The recursive function begins by processing i.e., adding to the array or printing the current node.
- Traverse Left Subtree: Recursively traverse the left subtree by invoking the preorder function on the left child of the current node. This step continues the exploration of nodes in a depth-first manner.
- Traverse Right Subtree: After traversing the entire left subtree, we traverse the right subtree recursively. We once again invoke the preorder function, but this time on the right child of the current node.

Dry Run

Algorithm:

Step 1: Check for the base case that if the current node is null, exit the void function.
Step 2: Push the value of the current node into the preorder traversal array.
Step 3: Invoke the preorder function on the left child then right child to traverse the left and right subtrees in the preorder manner respectively.

This recursive approach implicitly uses the call stack to handle backtracking while exploring the tree nodes.

#include <bits/stdc++.h>
using namespace std;

// Definition for a binary tree node
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;

    // Constructor to initialize a node with a value
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    // Helper function to perform preorder traversal
    void func(TreeNode* node, vector<int>& ans) {
        // If the current node is null, return (base case for recursion)
        if (node == nullptr) {
            return;
        }

        // Append the current node's value to the list
        ans.push_back(node->data);
        // Recursively traverse the left subtree
        func(node->left, ans);
        // Recursively traverse the right subtree
        func(node->right, ans);
    }

    // Function to initiate preorder traversal and return the resulting vector
    vector<int> preorder(TreeNode* root) {
        // Create an empty vector to store preorder traversal values
        vector<int> ans;
        // Call the helper function with the root node and the vector
        func(root, ans);
        // Return the resulting vector containing preorder traversal values
        return ans;
    }
};

// Main function to test the preorder traversal
int main() {
    // Creating a sample binary tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    // Create an instance of the Solution class
    Solution solution;
    // Getting preorder traversal
    vector<int> result = solution.preorder(root);

    // Displaying the preorder traversal result
    cout << "Preorder Traversal: ";
    for (int val : result) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}
import java.util.ArrayList;
import java.util.List;

// Definition for a binary tree node
public class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

    // Constructor to initialize a node with a value
    TreeNode(int val) {
        this.data = val;
        this.left = null;
        this.right = null;
    }
}

class Solution {
    // Helper function to perform preorder traversal
    private void func(TreeNode node, List<Integer> ans) {
        // If the current node is null, return (base case for recursion)
        if (node == null) {
            return;
        }

        // Append the current node's value to the list
        ans.add(node.data);
        // Recursively traverse the left subtree
        func(node.left, ans);
        // Recursively traverse the right subtree
        func(node.right, ans);
    }

    // Function to initiate preorder traversal and return the resulting list
    public List<Integer> preorder(TreeNode root) {
        // Create an empty list to store preorder traversal values
        List<Integer> ans = new ArrayList<>();
        // Call the helper function with the root node and the list
        func(root, ans);
        // Return the resulting list containing preorder traversal values
        return ans;
    }

    // Main method to test the preorder traversal
    public static void main(String[] args) {
        // Creating a sample binary tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        // Create an instance of the Solution class
        Solution solution = new Solution();
        // Getting preorder traversal
        List<Integer> result = solution.preorder(root);

        // Displaying the preorder traversal result
        System.out.print("Preorder Traversal: ");
        for (int val : result) {
            System.out.print(val + " ");
        }
        System.out.println();
    }
}
# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    # Helper function to perform preorder traversal
    def func(self, node, ans):
        # If the current node is None, return (base case for recursion)
        if node is None:
            return
        
        # Append the current node's value to the list
        ans.append(node.val)
        # Recursively traverse the left subtree
        self.func(node.left, ans)
        # Recursively traverse the right subtree
        self.func(node.right, ans)
    
    # Function to initiate preorder traversal and return the resulting list
    def preorder(self, root):
        # Create an empty list to store preorder traversal values
        ans = []
        # Call the helper function with the root node and the list
        self.func(root, ans)
        # Return the resulting list containing preorder traversal values
        return ans

# Main function to test the preorder traversal
if __name__ == "__main__":
    # Creating a sample binary tree
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)

    # Create an instance of the Solution class
    solution = Solution()
    # Getting preorder traversal
    result = solution.preorder(root)

    # Displaying the preorder traversal result
    print("Preorder Traversal:", end=" ")
    # Output each value in the preorder traversal result
    for val in result:
        print(val, end=" ")
    print()
// Definition for a binary tree node
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    // Helper function to perform preorder traversal
    func(node, ans) {
        // If the current node is null, return (base case for recursion)
        if (node === null) {
            return;
        }

        // Append the current node's value to the list
        ans.push(node.val);
        // Recursively traverse the left subtree
        this.func(node.left, ans);
        // Recursively traverse the right subtree
        this.func(node.right, ans);
    }

    // Function to initiate preorder traversal and return the resulting list
    preorder(root) {
        // Create an empty list to store preorder traversal values
        const ans = [];
        // Call the helper function with the root node and the list
        this.func(root, ans);
        // Return the resulting list containing preorder traversal values
        return ans;
    }
}

// Main function to test the preorder traversal
function main() {
    // Creating a sample binary tree
    const root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(3);
    root.left.left = new TreeNode(4);
    root.left.right = new TreeNode(5);

    // Create an instance of the Solution class
    const solution = new Solution();
    // Getting preorder traversal
    const result = solution.preorder(root);

    // Displaying the preorder traversal result
    console.log("Preorder Traversal:", result.join(" "));
}

// Run the main function to test the code
main();

Complexity Analysis :

Time Complexity: O(N) where N is the number of nodes in the binary tree, as each node of the binary tree is visited exactly once.

Space Complexity: O(N) where N is the number of nodes in the binary tree, as an additional space for the array is allocated to store the values of all ‘N’ nodes of the binary tree.

Intuition

As a prerequisite to this approach, please understand Preorder Traversal in detail. The preorder traversal of a Binary Tree follows the order: Root, Left then Right. An iterative approach maintains a stack structure to simulate the recursive nature of the traversal without using actual recursion. The stack follows a last-in-first-out methodology and stores the nodes yet to be processed mimicking the depth-first search characteristic of preorder traversal.

Approach

Initially, the root node is pushed into the stack. While the stack is not empty, we continuously pop nodes from the stack and for each popped node, we add its value to the resultant traversal vector, push its right child onto the stack followed by its left child.
This sequence ensures that the left child, which should be processed first in the preorder traversal, is visited before the right child due to the Last In, First Out behaviour of the stack. This process continues until all nodes are processed.

Dry Run

Algorithm:

Step 1: Initialise an empty vector ‘preorder’ to store the preorder traversal result. Create a stack to store the nodes during traversal and push the root node onto the stack. Check if the root is null, return an empty traversal result if true.
Step 2: Push the root of the binary tree into the stack.

Step 3: While the stack is not empty:
- Get the current node from the top of the stack.
- Remove the node from the stack.
- Add the node’s value to the preorder traversal result.
- First, push the right child onto the stack if it exists.
- Secondly, push the left child onto the stack if it exists.
Step 4: Return the ‘preorder’ traversal result.

#include <bits/stdc++.h>
using namespace std;

// Define the TreeNode structure
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : data(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    // Function to perform preorder traversal
    // of a binary tree iteratively
    vector<int> preorder(TreeNode* root) {
        // Initialize vector to store
        // the preorder traversal result
        vector<int> preorder;
        
        // If the root is null, return
        // an empty traversal result
        if(root == nullptr) {
            return preorder;
        }
        
        // Create a stack to store
        // nodes during traversal
        stack<TreeNode*> st;
        // Push the root node
        // onto the stack
        st.push(root);
        
        // Perform iterative preorder traversal
        while(!st.empty()) {
            // Get the current node
            // from the top of the stack
            root = st.top();
            // Remove the node
            // from the stack
            st.pop();
            
            // Add the node's value to
            // the preorder traversal result
            preorder.push_back(root->data);
            
            // Push the right child
            // onto the stack if exists
            if(root->right != nullptr) {
                st.push(root->right);
            }
            
            // Push the left child onto
            // the stack if exists
            if(root->left != nullptr) {
                st.push(root->left);
            }
        }
        
        // Return the preorder
        // traversal result
        return preorder;
    }
};

int main() {
    // Creating a binary tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    // Initializing the Solution class
    Solution sol;

    // Getting the preorder traversal
    vector<int> result = sol.preorder(root);

    // Displaying the preorder traversal result
    cout << "Preorder Traversal: ";
    for (int val : result) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}
import java.util.*;

// Define the TreeNode structure
class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        data = x;
        left = null;
        right = null;
    }
}

class Solution {
    // Function to perform preorder traversal
    // of a binary tree iteratively
    public List<Integer> preorder(TreeNode root) {
        // Initialize list to store
        // the preorder traversal result
        List<Integer> preorder = new ArrayList<>();

        // If the root is null, return
        // an empty traversal result
        if (root == null) {
            return preorder;
        }

        // Create a stack to store
        // nodes during traversal
        Stack<TreeNode> st = new Stack<>();
        // Push the root node
        // onto the stack
        st.push(root);

        // Perform iterative preorder traversal
        while (!st.empty()) {
            // Get the current node
            // from the top of the stack
            root = st.pop();

            // Add the node's value to
            // the preorder traversal result
            preorder.add(root.data);

            // Push the right child
            // onto the stack if exists
            if (root.right != null) {
                st.push(root.right);
            }

            // Push the left child onto
            // the stack if exists
            if (root.left != null) {
                st.push(root.left);
            }
        }

        // Return the preorder
        // traversal result
        return preorder;
    }
}

public class Main {
    public static void main(String[] args) {
        // Creating a binary tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        // Initializing the Solution class
        Solution sol = new Solution();

        // Getting the preorder traversal
        List<Integer> result = sol.preorder(root);

        // Displaying the preorder traversal result
        System.out.print("Preorder Traversal: ");
        for (int val : result) {
            System.out.print(val + " ");
        }
        System.out.println();
    }
}
from typing import List

# Define the TreeNode structure
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    # Function to perform preorder traversal
    # of a binary tree iteratively
    def preorder(self, root: TreeNode) -> List[int]:
        # Initialize list to store
        # the preorder traversal result
        preorder = []
        
        # If the root is None, return
        # an empty traversal result
        if root is None:
            return preorder
        
        # Create a stack to store
        # nodes during traversal
        st = []
        # Push the root node
        # onto the stack
        st.append(root)
        
        # Perform iterative preorder traversal
        while st:
            # Get the current node
            # from the top of the stack
            root = st.pop()
            
            # Add the node's value to
            # the preorder traversal result
            preorder.append(root.val)
            
            # Push the right child
            # onto the stack if exists
            if root.right:
                st.append(root.right)
            
            # Push the left child onto
            # the stack if exists
            if root.left:
                st.append(root.left)
        
        # Return the preorder
        # traversal result
        return preorder

# Creating a binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# Initializing the Solution class
sol = Solution()

# Getting the preorder traversal
result = sol.preorder(root)

# Displaying the preorder traversal result
print("Preorder Traversal:", end=" ")
for val in result:
    print(val, end=" ")
print()
class TreeNode {
    constructor(x) {
        this.data = x;
        this.left = null;
        this.right = null;
    }
}

class Solution {
    // Function to perform preorder traversal
    // of a binary tree iteratively
    preorder(root) {
        // Initialize array to store
        // the preorder traversal result
        let preorder = [];
        
        // If the root is null, return
        // an empty traversal result
        if (root === null) {
            return preorder;
        }
        
        // Create a stack to store
        // nodes during traversal
        let stack = [];
        // Push the root node
        // onto the stack
        stack.push(root);
        
        // Perform iterative preorder traversal
        while (stack.length > 0) {
            // Get the current node
            // from the top of the stack
            root = stack.pop();
            
            // Add the node's value to
            // the preorder traversal result
            preorder.push(root.data);
            
            // Push the right child
            // onto the stack if exists
            if (root.right !== null) {
                stack.push(root.right);
            }
            
            // Push the left child onto
            // the stack if exists
            if (root.left !== null) {
                stack.push(root.left);
            }
        }
        
        // Return the preorder
        // traversal result
        return preorder;
    }
}

// Creating a binary tree
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

// Initializing the Solution class
let sol = new Solution();

// Getting the preorder traversal
let result = sol.preorder(root);

// Displaying the preorder traversal result
console.log("Preorder Traversal: " + result.join(" "));

Complexity Analysis :

Time Complexity: O(N) where N is the number of nodes in the binary tree. Every node of the binary tree is visited exactly once, and for each node, the operations performed (pushing and popping from the stack, accessing node values, etc.) are constant time operations.

Space Complexity: O(N) where N is the number of nodes in the binary tree. This is because the stack can potentially hold all nodes in the tree when dealing with a skewed tree (all nodes have only one child), consuming space proportional to the number of nodes. In the average case or for a balanced tree, the maximum number of nodes that could be in the stack at any given time would be roughly the height of the tree, hence O(log2N).

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Complexity Analysis :

Intuition

Approach

Dry Run

Complexity Analysis :

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code