Pre-order Traversal (Recursive) - Binary Tree
To do a pre-order traversal of a binary tree recursively, we just use the definition of pre-order traversal: starting at the root, visit root, then visit the left subtree pre-order, then visit the right subtree pre-order:
void preorder(Node *root) {
if (root == nullptr) return;
cout << root->value << '\n';
preorder(root->left);
preorder(root->right);
}
Time complexity
The time complexity is O(n) (where n is the number of nodes in the tree) because that's the total work done when we combine the work done by each recursive call. See the video for more detail.
Space complexity
The space complexity is O(h) (where h is the height of the tree) because of the space taken by the call stack. See the video for more detail.