For traversing a (non-empty) binary tree in pre-order fashion, we must do these three things for every node N
starting from root node of the tree:
- (N) Process
N
itself. - (L) Recursively traverse its left subtree. When this step is finished we are back at N again.
- (R) Recursively traverse its right subtree. When this step is finished we are back at N again.
Complexity Analysis
Implementation
// Recursive function to perform pre-order traversal of the tree
public static void preorder(TreeNode root)
{
// return if the current node is empty
if (root == null) {
return;
}
// Display the data part of the root (or current node)
System.out.print(root.data + " ");
// Traverse the left subtree
preorder(root.left);
// Traverse the right subtree
preorder(root.right);
}