LC144. Binary Tree Preorder Traversal¶

Problem Description¶

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

Clarification¶

-

Assumption¶

-

Solution¶

Approach - Recursion¶

We can recursively traverse the tree in pre-order by defining a new helper function preorder. In the helper function,

values.append(root.val)  # visit root/parent node
preorder(root.left, values)  # recursively traverse the left subtree
preorder(root.right, values)  # recursively traverse the right subtree

Python

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        value_list = []
        self.preorder(root, value_list)
        return value_list

    def preorder(self, root: Optional[TreeNode],
            value_list: List[int]) -> None:
        if root is None:
            return

        value_list.append(root.val)
        self.preorder(root.left, value_list)
        self.preorder(root.right, value_list)

Complexity Analysis of Approach 1¶

Time complexity: $O(n)$
The algorithm will visit all nodes exact once via recursive function call and therefore the time complexity is $O(n)$.
Space complexity: $O(n)$
- Recursive function call takes $O(h)$ space for the call stack. The $h$ is the height of the binary tree, which could be the total number of nodes $n$ in the worst case.
- The return list takes $O(n)$ space to save all node values.
- The total space complexity is $O(n) = O(h) + O(n)$.

Approach 2 - Iteration¶

We can also iteratively traverse the tree, traverse the root and left first and use stack to store right nodes that will be visited later.

python

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        values = []
        stack = deque()

        curr_node = root
        while curr_node or stack:
            if curr_node:
                values.append(curr_node.val)
                stack.append(curr_node)  # To return the root later.
                curr_node = curr_node.left
            else:
                curr_node = stack.pop()
                curr_node = curr_node.right

        return values

Complexity Analysis of Approach 2¶

Time complexity: $O(n)$
Each node (total $n$ nodes) is pushed once to and popped once from the stack. So the time complexity is $O(2n) = O(n)$.
Space complexity: $O(n)$
- The stack needs to store the right nodes which could be $n$ in the worst case.
- The return list takes $O(n)$ space to save all node values.
- The total space complexity is $O(n) = O(n) + O(n)$.

Approach 3 - Morris Traversal¶

We can use Morris Traversal to visit nodes by using temporary links instead of using recursion and stack. It modifies the tree temporarily. The general idea is to

Before exploring the left tree, find the rightmost node in the left tree. That's also the last node to visit in the left tree.
Establish a temporary link between the rightmost node and the current node. So it can come back after exploring the left tree.
Then explore the left tree (use similar approach). When it comes back to the current node with the temporary link, it indicates the left sub-tree has visited.