144. Binary Tree Preorder Traversal

The Question

For this article we will be covering Leetcode '144. Binary Tree Preorder Traversal' question. This question is rated as a easy question.

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

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

Explaining The Question

The question explains itself pretty well. We're going to need to perform pre-order Depth First Search on the binary tree. We're going to add the root value to an array every time we visit a new node.

Now this is a trivial issue if you're familiar with all of the binary tree traversal algorithms. But if you're not, you'll need to think about this.

Learning Depth First Search and all of of it's traversal is mandatory knowledge for the majority of Binary Tree questions. I highly suggest you master the traversals below.

• Depth First Search:

  • Pre-order
  • In-order
  • Post-order

• Leetcode Questions

  • Binary Tree Preorder Traversal
  • Binary Tree Inorder Traversal
  • Binary Tree Postorder Traversal

---

Recommended Knowledge

1. Binary Tree
2. Depth First Search
3. Recursion
4. Call Stack

How we're going to do it:

The key to this question is to understand the Depth First Search algorithm. How we're going to visit everyone starting from the root, going to the left most node to the right most node until we have expired all of our nodes. At each point, we will add that nodes value to the list.

We're going to do this recursively.

1. Note, we declare a list variable within the functions parameters. As it will default to an empty array.
2. We firstly ask, 'Is the given node empty?' If it is, we return the list we have so far. If not, we add the node value to the list and then we recursively call the function on the left and right nodes.
3. We repeat the above algorithm until we have exhausted all of the nodes.
4. The list is returned at the end of the function.

Big O Notation:

• Time Complexity: O(n) | Where n is the number of nodes the tree has | As we will always be traversing the entire tree
• Space Complexity: O(h) | As we will be using the call Stack to store the nodes

Leetcode Results:

See Submission Link:

• Runtime: 59 ms faster than 91.84% of JavaScript online submissions for Binary Tree Preorder Traversal
• Memory Usage: 42.2 MB, less than 63.12% of JavaScript online submissions for Binary Tree Preorder Traversal

---

The Solution

var preorderTraversal = function (root, list = []) {

    /* -------------------------------------------------------------------------- */
    /*                     144. Binary Tree Preorder Traversal                    */
    /* -------------------------------------------------------------------------- */

    /**
     * @author  Samuel Hinchliffe
     * @see    {@link linkedin.com/in/samuel-hinchliffe-🚀-2bb5801a5/ | Author's Linkedin }
     * @see    {@link github.com/Samuel-Hinchliffe}
     */

    // We're at a empty node, so we return our list here
    // Just in case the list is empty, we return an empty list
    if (!root) {
        return list;
    }

    // We're at a non-empty node, so we add the value to our list
    // We're doing this in a preorder manner. 
    list.push(root.val);

    // Traverse to the left node and right nodes
    preorderTraversal(root.left, list);
    preorderTraversal(root.right, list);

    // We traversed this entire little tree
    // So let's return our list. 
    return list;
};

Comments

[Samuel Hinchliffe 🚀]

Hey There 👋

---

Thank you for taking the time to look at my solution. I hope you found it interesting and useful.

If you're having difficulties understanding this solution or just need some clarity on a certain section of it. Please do not hesitate to contact me. We're all in this together and I'm happy to help. 😁

---

Contact me here: