144. Binary Tree Preorder Traversal
Tags: leetcode, tutorial, algorithms, javascript
Published: 2022-04-24 14:02:01

## The Question
For this article we will be covering Leetcode '[144. Binary Tree Preorder Traversal](https://leetcode.com/problems/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]
```

![image](https://assets.leetcode.com/users/images/64b803bd-8b0e-4948-b08f-d9806f39b00d_1650805215.103034.gif)


## 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](https://en.wikipedia.org/wiki/Tree_traversal#Pre-order)
  * [In-order](https://en.wikipedia.org/wiki/Tree_traversal#In-order)
  * [Post-order](https://en.wikipedia.org/wiki/Tree_traversal#Post-order)

* Leetcode Questions
    * [Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal/description/)
    * [Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/description/)
    * [Binary Tree Postorder Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/description/)

***

##  Recommended Knowledge
1. [Binary Tree](https://en.wikipedia.org/wiki/Binary_tree)
2. [Depth First Search](https://en.wikipedia.org/wiki/Depth-first_search)
3. [Recursion](https://en.wikipedia.org/wiki/Recursion)
4. [Call Stack](https://en.wikipedia.org/wiki/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

[![LeetCode](https://img.shields.io/badge/LeetCode-000000?style=for-the-badge&logo=LeetCode&logoColor=#d16c06)](https://leetcode.com/submissions/detail/679828236/)


***

# 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;
};

```