144. Binary Tree Preorder Traversal

  

Binary Tree Preorder Traversal

Problem Description

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

Example 1:

Input: root = [1,null,2,3]
Output: [1,2,3]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

 

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100 

Follow up: Recursive solution is trivial, could you do it iteratively?

(Image from: https://github.com/MisterBooo/LeetCodeAnimation )

Approach) Stack

Code:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function (root) {
    const ans = [];
    const stack = [];
    let node = root;
    while (node !== null || stack.length !== 0) {
        while (node !== null) {
            ans.push(node.val);
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        node = node.right;
    }
    return ans;
};

Complexity 

Time Complexity
Time complexity will be O(n).


Space Complexity
space complexity should also be O(n).

Approach) Recursion

Code:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function (root) {
    const ans = [];
    preorder(root);
    return ans;

    function preorder(root) {
        if (root === null) {
            return;
        }
        ans.push(root.val);
        preorder(root.left);
        preorder(root.right);
    }
};

Complexity 

Time Complexity
Time complexity will be O(n).


Space Complexity
space complexity should also be O(n).

Conclusion

That’s all folks! In this post, we solved LeetCode problem #144. Binary Tree Preorder Traversal

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!