LeetCode: 144. Binary Tree Preorder Traversal

The problem

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

Example

Input:  [1,null,2,3]
Output: [1,2,3]

Understanding the problem

Tree traversal is a fundamental concept in computer science, particularly when working with hierarchical data structures like trees. Preorder tree traversal is one of the essential techniques used to explore and process the nodes of a tree. In this blog post, we will delve into the concept of preorder traversal and break down a C++ code example that demonstrates how to implement it step by step.

Preorder Tree Traversal: Preorder traversal is a method of visiting the nodes of a binary tree in a specific order. In preorder traversal, you start from the root node and visit the nodes in the following order: root, left subtree, right subtree. This order helps you process the tree's nodes in a top-down manner.

Solution

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ans;
    preorderNode(ans, root);
    return ans;
}

void preorderNode(vector<int> &arr, TreeNode *node){
    if(node == nullptr) return;

    arr.push_back(node->val);
    preorderNode(arr, node->left);
    preorderNode(arr, node->right);
}

Understanding the solution, Preorder Tree Traversal in C++

The preorderTraversal function serves as the entry point for initiating the preorder traversal process. It takes a single argument, root, which represents the root node of the binary tree. The function initializes an empty vector ans, which will eventually store the values of the tree nodes in preorder traversal order.

The preorderNode function is a helper function that performs the actual preorder traversal. It takes two parameters: a reference to the vector arr and a pointer to a TreeNode named node.

• The function first checks if the current node is nullptr, which indicates the end of a branch or subtree. If the node is null, the function returns, effectively stopping the traversal for that branch.
• If the node is not null, the function adds the value of the current node (node->val) to the arr vector. This step captures the top-down traversal order.
• The function then recursively calls preorderNode on the left subtree (node->left) and the right subtree (node->right). This recursive process ensures that the left subtree is explored before the right subtree, in line with the preorder traversal approach.