# 144. Binary Tree Preorder Traversal

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

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,2,3]

# Solution

Approach 1: recursion.

Approach 2: stack based -- visit the middle node, then push the right then left substree in stack.

Approach 3: stack based -- visit the middle node, then navigate down the left subtree, while keeping the right subtree in stack.

Approach 4: Morris traversal: stackless (saves space). It keeps track of the 'next' node (the top node to return to) by setting the right pointer of the rightmost leaf in the left subtree (and deleting these pointers later). Running time is tricky: the outer loop visits each node once -- O(N). The inner loop means each node needs to find it's prev (rightmost leaf on left subtree) twice. If you trace find prevs for all nodes in a tree, they add up to traversing every edge of a tree, and a tree of N nodes has N-1 edges. So the inner loops runs in O(N) cumulatively.

# Code (Python)

Approach 1:

    def preorderTraversal(self, root):
        # recursive
        if not root:
            return []
        return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)

Approach 2:

    def preorderTraversal(self, root):
        # iterative, stack based
        if not root:
            return []
        stack, result = [root], []
        while stack:
            node = stack.pop()
            result.append(node.val)
            # left subtree gets explored before right
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return result

Approach 3:

    def preorderTraversal(self, root):
        # iterative, stack based
        if not root:
            return []
        stack, result = [root], []
        while stack:
            current = stack.pop()
            # navigate down the left subtree while keeping the right subtree to be explored
            while current:
                result.append(current.val)
                stack.append(current.right) # "push horizontal"
                current = current.left
        return result

Approach 4:

    def preorderTraversal(self, root):
        # Morris traversal
        if not root:
            return []
        result = []
        node = root
        while node:
            if not node.left: # happens either when a node doesn't have a left child, or a leaf node having a pseudolink
                result.append(node.val)
                node = node.right
            else:
                # for this node, search for the rightmost leaf on its left subtree (called 'prev', the last node to visit before it goes back to this node)
                prev = node.left
                while prev.right and prev.right != node:
                    prev = prev.right
                if not prev.right:
                    # set the pseudolink
                    prev.right = node
                    result.append(node.val)
                    node = node.left
                else: # prev.right == node --> we got to the back pointer
                    prev.right = None
                    node = node.right
        return result

# Code (C++)

Approach 1:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
// Recursion.
class Solution {
private:
    vector<int> preorder;
    void doPreorderTraversal(TreeNode* root) {
        if (root == NULL)
            return;
        preorder.push_back(root->val);
        doPreorderTraversal(root->left);
        doPreorderTraversal(root->right);
    }
public:
    vector<int> preorderTraversal(TreeNode* root) {
        doPreorderTraversal(root);
        return preorder;
    }
};

Approach 2:

// Iteration.
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> preorder;
        stack<TreeNode*> st;
        if (root)
            st.push(root);
        while (!st.empty())
        {
            TreeNode *curr = st.top();
            st.pop();
            preorder.push_back(curr->val);
            if (curr->right)
                st.push(curr->right);
            if (curr->left)
                st.push(curr->left);
        }
        return preorder;
    }
};

Approach 3:

// Iteration.
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> preorder;
        stack<TreeNode*> st;
        TreeNode *curr = root;
        while (curr)
        {
            preorder.push_back(curr->val);
            if (curr->right)
                st.push(curr->right);
            curr = curr->left;
            if (!curr && !st.empty())
            {   
                curr = st.top();
                st.pop();
            }
        }
        return preorder;
    }
};

Approach 4:

// Morris traversal.
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> preorder;
        TreeNode *curr = root;
        while (curr)
        {
            // Get the rightmost leaf of the left subtree.
            TreeNode *leftRightmost = curr->left;
            while (leftRightmost && leftRightmost->right)
                leftRightmost = leftRightmost->right;
            if (leftRightmost)
                leftRightmost->right = curr->right;
            if (curr->left)
                curr->right = curr->left;
            curr->left = NULL;
            preorder.push_back(curr->val);
            curr = curr->right;
        }
        return preorder;
    }
};