Binary Tree Preorder Traversal Algorithm
The Binary Tree Preorder Traversal Algorithm is a tree traversal technique used to traverse and process the nodes of a binary tree in a specific order, which is the root node first, followed by the left subtree, and then the right subtree. It is a depth-first traversal method, meaning it processes nodes by exploring as far as possible along a branch before backtracking. The algorithm is commonly used for various applications, such as searching for a particular value, inserting a new node, and deleting a node in a binary tree data structure.
In the Preorder Traversal Algorithm, the process starts at the root node of a binary tree, and it is visited first. After visiting the root node, the algorithm recursively traverses the left subtree of the root node, followed by the right subtree. The process is repeated until all nodes in the binary tree have been visited and processed. This traversal technique can be implemented both iteratively and recursively, with the recursive approach being more straightforward and easier to understand. However, the iterative approach can be more efficient in terms of time and memory usage, as it avoids the overhead of recursive function calls.
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
vector<int> result;
TreeNode* node = root;
while (node) {
if (node->left == NULL) {
result.push_back(node->val);
node = node->right;
} else {
TreeNode* next = node->left;
while (next->right && next->right != node) {
next = next->right;
}
if (next->right == NULL) {
next->right = node;
result.push_back(node->val);
node = node->left;
} else {
next->right = NULL;
node = node->right;
}
}
}
return result;
}
};
