##### Binary Tree Structure:

- A binary tree is a tree data structure where each node has at most two children: a left child and a right child.
- The topmost node of a binary tree is called the root node.
- Each node in a binary tree can have either zero, one, or two child nodes.
- The child nodes of a binary tree are ordered, typically with the left child node being smaller or equal to the parent node and the right child node being greater.
- Nodes that do not have any children are called leaf nodes.
- The height of a binary tree is the length of the longest path from the root node to any leaf node.
- The depth of a node in a binary tree is the length of the path from the root node to that node.
- Binary trees can be of different types, such as full binary trees, complete binary trees, balanced binary trees, and more, based on specific characteristics and properties.
- Binary trees can be represented using various data structures such as linked lists, arrays, or objects with references to child nodes.
- Binary trees are commonly used for efficient searching, sorting, and organizing data in a hierarchical manner.

##### Types of Tree Travels:

The process of viewing each node in a binary tree in a specified order is referred to as binary tree traversal. There are three popular traversal techniques:

**In-order Traversal:**- Visit the left subtree recursively.
- Visit the current node.
- Visit the right subtree recursively.
- In an in-order traversal of a binary search tree, the nodes will be visited in ascending order.

**Pseudo-code:**

```
void Inorder(struct node* ptr)
{
if(ptr != NULL)
{
Inorder(ptr->left);
printf("%d", ptr->data);
Inorder(ptr->right);
}
}
```

**Pre-order Traversal:**- Visit the current node.
- Visit the left subtree recursively.
- Visit the right subtree recursively.
- Pre-order traversal is useful for creating a copy of the tree or making a prefix expression of an expression tree.

**Pseudo-code:**

```
void Preorder(struct node* ptr)
{
if(ptr != NULL)
{
printf("%d", ptr->data);
Preorder(ptr->left);
Preorder(ptr->right);
}
}
```

**Post-order Traversal:**- Visit the left subtree recursively.
- Visit the right subtree recursively.
- Visit the current node.
- Post-order traversal is useful for deleting the tree or evaluating an expression tree.

**Pseudo-code:**

```
void Postorder(struct node* ptr)
{
if(ptr != NULL)
{
Postorder(ptr->left);
Postorder(ptr->right);
printf(“%d”, ptr->data);
}
}
```

In addition to the above three basic traversals, there are two more specialized traversals:

**Level-order Traversal (Breadth-first Traversal):**- Visit the nodes at each level from left to right, starting from the root and moving downwards.
- This traversal uses a queue data structure to visit the nodes in a breadth-first manner.

**Pseudo-code:**

```
void levelOrderTraversal(struct Node* root) {
// Check if the tree is empty
if (root == NULL)
return;
// Create a queue for level-order traversal
struct Node** queue = (struct Node**)malloc(sizeof(struct Node*));
int front = 0;
int rear = 0;
// Enqueue the root node
queue[rear] = root;
rear++;
while (front < rear) {
// Dequeue a node from the queue
struct Node* current = queue[front];
front++;
// Process the current node
printf("%d ", current->data);
// Enqueue the left child if it exists
if (current->left != NULL) {
queue = (struct Node**)realloc(queue, (rear + 1) * sizeof(struct Node*));
queue[rear] = current->left;
rear++;
}
// Enqueue the right child if it exists
if (current->right != NULL) {
queue = (struct Node**)realloc(queue, (rear + 1) * sizeof(struct Node*));
queue[rear] = current->right;
rear++;
}
}
// Free the memory allocated for the queue
free(queue);
}
```

**Reverse In-order Traversal:**- Visit the right subtree recursively.
- Visit the current node.
- Visit the left subtree recursively.
- Reverse in-order traversal is useful for visiting the nodes in descending order in a binary search tree.

##### Time and Space Complexities for different tree traversal algorithms:

Traversal Algorithm | Time Complexity | Space Complexity |
---|---|---|

Preorder | O(n) | O(h) |

Inorder | O(n) | O(h) |

Postorder | O(n) | O(h) |

Level-order | O(n) | O(w) |

Note:

- n is the number of nodes in the tree.
- h is the height of the tree.
- w is the maximum width (maximum number of nodes at any level) of the tree.

In the worst case, the space complexity for all traversals can be O(n) for a skewed tree, where the height of the tree is equal to the number of nodes.

*Note: also read about* Queues in DSA

**Follow Me**

If you like my post please follow me to read my latest post on programming and technology.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py

Staying up to the mark is what defines me. Hi all! I’m Rabecca Fatima a keen learner, great enthusiast, ready to take new challenges as stepping stones towards flying colors.