Categories
28°C, New York
Home C Language Preorder Traversal of Binary Tree in C

Preorder Traversal of Binary Tree in C

Algorithm for Pre-Order Binary Tree Traversal

Preorder traversal is a DFS tree traversal technique that first visits the current node, traverses the left sub-tree as far as it can and then traverses the right sub-tree.

Pre-order Traversal

  1. Visit the root node.
  2. Then, recursively traverse the left subtree.
  3. Finally, recursively traverse the right subtree.

Consider the following example,

For preorder traversal of the above tree:

  1. Start at the root node (1).
  2. Visit the root node then print it.
  3. Traverse the left subtree of the root (2).
  4. Visit the root of the left subtree (2) and print it.
  5. Traverse the left subtree of the node 2(4) and visit 4 and print it.
  6. Backtrack to the node 2 and traverse its right subtree (5) and visit and print it.
  7. Backtrack to the root node (1).
  8. Traverse the right subtree of root (3).
  9. Visit the root of the right subtree (3) and print it.

The pre-order traversal of the binary tree: 1, 2, 4, 5, 3

Preorder Tree Traversal of Binary Tree in C

A binary tree is a hierarchical data structure composed of nodes where each node has at most two children. It can referred to as the left child and the right child. Due to having a non-linear structure, a binary tree can be traversed in multiple ways. One such way is preorder traversal which is a Depth First (DFS) Traversal technique.

In this article, we will learn how to implement preorder binary tree traversal in C and analyze its space and time complexity.

Similar Reads

Preorder Traversal of Binary Tree in C

Preorder traversal is a DFS tree traversal technique that first visits the current node, traverses the left sub-tree as far as it can and then traverses the right sub-tree....

Algorithm for Pre-Order Binary Tree Traversal

Following is the algorithm of the pre-order binary tree traversal:...

C++ Program to Implement Preorder Traversal of the Binary Tree

C // C Program to illustrate how to implement the preorder // binary tree traversal #include #include // creating tree node struct TreeNode { int val; struct TreeNode* left; struct TreeNode* right; }; // utility function to create a node with given value struct TreeNode* createNode(int val) { struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode)); newNode->val = val; newNode->left = NULL; newNode->right = NULL; return newNode; } // preorder traversal void preorderTraversal(struct TreeNode* root) { // if the current node is empty if (root == NULL) return; // visiting node printf("%d ", root->val); // going to left subtree preorderTraversal(root->left); // going to right subtree preorderTraversal(root->right); } // drive code int main() { // creating example tree struct TreeNode* root = createNode(1); root->left = createNode(2); root->right = createNode(3); root->left->left = createNode(4); root->left->right = createNode(5); printf("Preorder Traversal: "); preorderTraversal(root); return 0; }...

Applications

Following are some major application of the preorder binary tree traversal:...

Tags:
#C-DSA #C Language

Algorithm for Pre-Order Binary Tree Traversal