Leetcode 144. Binary Tree Preorder Traversal

Problem Explanation

A Binary Tree is a data structure with a very specific structure. Each node in a tree can have two immediate children - a left child and a right child. The objective of this problem is to return the preorder traversal of a binary tree. The preorder traversal of a tree is a process where you visit each node in the following order: current node, then left child, and finally the right child.

For example, if we consider the binary tree as:

1
2
3   1
4    \
5     2
6    /
7   3

The preorder traversal of this tree would be: [1, 2, 3]

Approach

A simple way to solve this problem is by using a recursive function. The base case of the recursion will be when the current node is null. If the current node is not null, we first add the value of the current node to our result list, then we recursively traverse the left child, and finally the right child.

Let's go through an example to better understand how this works:

Example

Consider the same binary tree as before:

1
2
3   1
4    \
5     2
6    /
7   3

• We start at the root node (1). Since it's not null, we add it to our result list. The result becomes: [1].
• We then recursively traverse the left child. Since it's null, nothing happens.
• We then recursively traverse the right child (2). Since it's not null, we add it to our result list. The result becomes: [1, 2].
  • We recursively traverse the left child of 2 (3). Since it's not null, we add it to our result list. The result becomes: [1, 2, 3].
  • We recursively traverse the right child of 2. Since it's null, nothing happens.
• After all the recursion, our final result is: [1, 2, 3]

As such, we've completed the preorder traversal of the binary tree.

Solution

Python

1
2python
3class Solution:
4  def preorderTraversal(self, root):
5    ans = []
6    self.preorder(root, ans)
7    return ans
8
9  def preorder(self, root, ans):
10    if root is None:
11      return
12    ans.append(root.val)
13    self.preorder(root.left, ans)
14    self.preorder(root.right, ans)

Java

1
2java
3class Solution {
4  public List<Integer> preorderTraversal(TreeNode root) {
5    List<Integer> ans = new ArrayList<>();
6    preorder(root, ans);
7    return ans;
8  }
9
10  private void preorder(TreeNode root, List<Integer> ans) {
11    if (root == null) {
12      return;
13    }
14    ans.add(root.val);
15    preorder(root.left, ans);
16    preorder(root.right, ans);
17  }
18}

JavaScript

1
2javascript
3var preorderTraversal = function(root) {
4  let ans = [];
5  function preorder(node) {
6    if (node === null) {
7      return;
8    }
9    ans.push(node.val);
10    preorder(node.left);
11    preorder(node.right);
12  }
13  preorder(root);
14  return ans;
15};

C++

1
2cpp
3class Solution {
4public:
5    vector<int> preorderTraversal(TreeNode* root) {
6        vector<int> ans;
7        preorder(root, ans);
8        return ans;
9    }
10
11private:
12    void preorder(TreeNode* root, vector<int>& ans) {
13        if (root == nullptr) {
14            return;
15        }
16        ans.push_back(root->val);
17        preorder(root->left, ans);
18        preorder(root->right, ans);
19    }
20};

C#

1
2csharp
3public class Solution {
4    public IList<int> PreorderTraversal(TreeNode root) {
5        List<int> ans = new List<int>();
6        Preorder(root, ans);
7        return ans;
8    }
9    
10    private void Preorder(TreeNode root, List<int> ans) {
11        if (root == null) {
12            return;
13        }
14        ans.Add(root.val);
15        Preorder(root.left, ans);
16        Preorder(root.right, ans);
17    }
18}

Conclusion

The approach discussed above allows us to implement preorder traversal of a binary tree, in various programming languages such as Python, Java, JavaScript, C++, and C#. Preorder traversal is a common task when working with binary trees, and understanding it can help you solve many other similar problems in data structures and algorithms.

Whether you are preparing for coding interviews or trying to refresh your data structure and algorithm skills, this type of recursive binary tree question is a must-try. The key takeaway from this topic is the understanding of handling recursion in tree-based algorithms and how to design the solution in different programming languages.

The time complexity of the above approach is O(N), where N is the number of nodes in the tree. This is because we need to visit each node once to add its value to the result list. The space complexity is also O(N). In the worst-case scenario, if the tree is completely unbalanced, e.g., each node only has a left child, the recursive call will be called N times (the size of the call stack), therefore, the space complexity is O(N). But in the best case (the tree is completely balanced), the height of the tree would be log(N), and the space complexity would be O(log(N)).

But remember, recursion has a cost (it isn't free!) and too deep a recursion could result in a stack overflow. Therefore, always test and scrutinize your recursive code, especially for edge-cases like trees with only one or two nodes or even an empty tree.