{x}
blog image

Binary Tree Preorder Traversal

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

 

Example 1:

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

Output: [1,2,3]

Explanation:

Example 2:

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]

Output: [1,2,4,5,6,7,3,8,9]

Explanation:

Example 3:

Input: root = []

Output: []

Example 4:

Input: root = [1]

Output: [1]

 

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100

 

Follow up: Recursive solution is trivial, could you do it iteratively?

144. Binary Tree Preorder Traversal

This problem asks for a preorder traversal of a binary tree. Preorder traversal follows the pattern: Root -> Left -> Right. We'll explore three solutions: recursive, iterative using a stack, and iterative using Morris traversal (constant space).

Solution 1: Recursive Approach

This is the most straightforward approach. The function recursively visits the root, then the left subtree, and finally the right subtree.

Time Complexity: O(N), where N is the number of nodes. Each node is visited exactly once.

Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be N. In the best case (a balanced tree), H is logâ‚‚N.

Code:

Python:

class Solution:
    def preorderTraversal(self, root):
        result = []
        self._preorder(root, result)
        return result
 
    def _preorder(self, node, result):
        if node:
            result.append(node.val)
            self._preorder(node.left, result)
            self._preorder(node.right, result)

Java:

class Solution {
    List<Integer> result = new ArrayList<>();
 
    public List<Integer> preorderTraversal(TreeNode root) {
        preorder(root);
        return result;
    }
 
    private void preorder(TreeNode node) {
        if (node != null) {
            result.add(node.val);
            preorder(node.left);
            preorder(node.right);
        }
    }
}

C++:

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        preorder(root, result);
        return result;
    }
 
private:
    void preorder(TreeNode* node, vector<int>& result) {
        if (node) {
            result.push_back(node->val);
            preorder(node.left, result);
            preorder(node.right, result);
        }
    }
};

Solution 2: Iterative Approach using Stack

This approach uses a stack to simulate the recursive calls. We push nodes onto the stack and process them in a last-in, first-out (LIFO) manner.

Time Complexity: O(N) - Each node is visited once.

Space Complexity: O(H) - In the worst case (a skewed tree), the stack can grow to the height of the tree (H). This is the same as the recursive approach's space complexity.

Code:

Python:

class Solution:
    def preorderTraversal(self, root):
        result = []
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                result.append(node.val)
                stack.append(node.right)
                stack.append(node.left)  # Push left after right to maintain preorder
        return result

Java:

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node != null) {
                result.add(node.val);
                stack.push(node.right);
                stack.push(node.left);
            }
        }
        return result;
    }
}

C++:

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

Solution 3: Morris Traversal (Constant Space)

Morris traversal is an in-place algorithm that avoids both recursion and explicit stack usage. It cleverly uses the tree's structure itself to maintain traversal order.

Time Complexity: O(N) - Each node is visited a constant number of times.

Space Complexity: O(1) - Constant extra space is used. This is the most space-efficient approach.

Code: (Illustrative Python example - Adapting to other languages requires careful handling of pointers/references)

class Solution:
    def preorderTraversal(self, root):
        result = []
        curr = root
        while curr:
            if curr.left is None:  # No left child, process current node
                result.append(curr.val)
                curr = curr.right
            else:  # Left child exists, find inorder predecessor
                prev = curr.left
                while prev.right and prev.right != curr:
                    prev = prev.right
                if prev.right is None:  # Link predecessor to current
                    result.append(curr.val)
                    prev.right = curr
                    curr = curr.left
                else:  # Unlink predecessor
                    prev.right = None
                    curr = curr.right
        return result

Remember to replace TreeNode with your specific tree node definition in your chosen language. The Morris traversal is more complex to implement but offers the best space efficiency. The recursive and iterative stack solutions are generally easier to understand and implement.