Binary Tree Preorder Traversal

Problem

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

Solution Approach

Expected Time complexity: $O(n)$

Click - to see solution code

C++

class Solution {
   public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> preorder;
        TreeNode* cur = root;
        while (cur != NULL) {
            if (cur->left == NULL) {
                preorder.push_back(cur->val);
                cur = cur->right;
            } else {
                TreeNode* prev = cur->left;
                while (prev->right && prev->right != cur) {
                    prev = prev->right;
                }

                if (prev->right == cur) {
                    prev->right = NULL;
                    cur = cur->right;
                } else {
                    prev->right = cur;
                    preorder.push_back(cur->val);
                    cur = cur->left;
                }
            }
        }
        return preorder;
    }
};