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
isnullptr
, 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 thearr
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.