Recursion

Preorder Traversal

This is a really basic problem to make sure you know how to implement a preorder traversal - you won't get something this easy in an interview.

Problem: Given the root node of a binary tree, return the preorder traversal of its nodes.

Example:

\notag \large \texttt{=> returns [1,2,3,4,5,6,7]}

Hint: Remember, the preorder traversal first does something on a node "pre" doing it on its children.

First Few Test Cases:

We want to do a preorder traversal over all the nodes in the tree.

1. Recursion

The recursion for a preorder traversal is to visit the current node, then all the nodes to the left, then right, c L R.

When we visit each node, we add its value to an array. Here's the recursion:

2. Base case

This recursion will keep calling itself on deeper and deeper nodes in the tree. Eventually, it calls itself on a null node, preorder(null). In this case, we don't want to traverse any further and we should just do nothing.

3. Code

To code the preorder traversal function, we just combine the recursion and base case. After calling this function, we return the values array that it filled in.

Time Complexity $O(n)$ . We walk through all of the nodes in the tree, which is $n$ nodes total.

Space Complexity $O(n)$ . The recursive function calls are stored inside of the Call Stack, which grows up to the depth of the tree. The tree might be a flat line, in which case it's $n$ nodes deep.

Mark as Completed:

Submits:

preorderArray

Imports:

TreeNode

Test your code to get an output here!

preorderArray(

)

Test your code to get an output here!