144. Binary Tree Preorder Traversal

Description

The problem involves performing a preorder traversal of a binary tree. In a preorder traversal, the nodes are visited in the following order: root, left subtree, and then right subtree. The task is to return the list of node values in the order they are visited.

Intuition

Preorder traversal can be thought of as the process of visiting a node before its children. This order is naturally recursive because at each node, we perform the same operation: visit the node, traverse the left subtree, and then traverse the right subtree. The recursive nature of trees makes recursion an intuitive way to solve this problem.

Approach

1. Recursive Function: - Create a helper function preOrder that takes the current node and a list res as arguments. - If the current node is null, return immediately. - Otherwise, add the node's value to the list res. - Recursively call the preOrder function on the left child, then on the right child.
2. Initialization: - Start by initializing an empty list res that will store the node values in preorder. - Call the preOrder function with the root of the tree and the list res. - Finally, return the list res which contains the preorder traversal of the tree.

Complexity

Time Complexity:

(O(N)), where (N) is the number of nodes in the tree. Each node is visited exactly once during the traversal.

Space Complexity:

• Recursive Call Stack: (O(H)), where (H) is the height of the tree. In the worst case, the height of the tree could be (O(N)) for a skewed tree.
• Auxiliary Space: (O(N)) for storing the result list res, which contains the node values.

Code

C++

class Solution {
public:
    void preOrder(TreeNode* root, std::vector& res) {
        if (root == nullptr) return;

        res.push_back(root->val);
        preOrder(root->left, res);
        preOrder(root->right, res);
    }

    std::vector preorderTraversal(TreeNode* root) {
        std::vector res;
        preOrder(root, res);
        return res;
    }
};

Python

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

class Solution:
    def preOrder(self, root, res):
        if not root:
            return

        res.append(root.val)
        self.preOrder(root.left, res)
        self.preOrder(root.right, res)

    def preorderTraversal(self, root):
        res = []
        self.preOrder(root, res)
        return res

Java

/*class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
*/
class Solution {
    private void preOrder(TreeNode root, List res) {
        if (root == null) return;

        res.add(root.val);
        preOrder(root.left, res);
        preOrder(root.right, res);
    }

    public List preorderTraversal(TreeNode root) {
        List res = new ArrayList<>();
        preOrder(root, res);
        return res;
    }
}

JavaScript

function preOrder (root, res) {

    if(root == null) return;

    else res.push(root.val);
    preOrder(root.left, res);
    preOrder(root.right, res);
};
var preorderTraversal = function(root) {
    
    let res = [];
    preOrder(root, res);
    return res;
};