Binary Tree Preorder Traversal

Preorder Traversal

Question

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

Example:

Input：{1,2,3}
Output：[1,2,3]
Explanation:
   1
  / \
 2   3
it will be serialized {1,2,3}
Preorder traversal


Input：{1,#,2,3}
Output：[1,2,3]
Explanation:
1
 \
  2
 /
3
it will be serialized {1,#,2,3}
Preorder traversal

Analyzation

Recursion

Follow the path of “Root -> Left -> Right” and do the recursion.

Note that “+=” is almost the same as “.extend” and the only difference is that the “.extend” evolves a function call so it is slightly more expensive in Python. Here we cannot use “.append” because in this way it will append empty lists because it is a recursive call.

The Code

class Solution {
    """
    @param root: A Tree
    @return: Preorder in ArrayList which contains node values.
    """
    def preorderTraversal(self, root):
        # write your code here
        result = []
        if root:
            result.extend([root.val])
            result.extend(self.preorderTraversal(root.left))
            result.extend(self.preorderTraversal(root.right))
        
        return result
}


class Solution:
    """
    @param root: A Tree
    @return: Preorder in ArrayList which contains node values.
    """
    def preorderTraversal(self, root):
        # write your code here
        result = []
        if root:
            result += [root.val]
            result += self.preorderTraversal(root.left)
            result += self.preorderTraversal(root.right)
        
        return result

Time & Space Complexity

• Time complexity: O(n). Remember that the best case of a Binary Tree is O(logn) since it is a balanced tree but the worst case is O(n) because it can skew to only one side.
• Space complexity: O(n). Remember that the space complexity is always about how many nodes there are in a Binary Tree. If the tree is well-balanced then it is O(logn) but the worst case will be O(n).