# Binary Trees: Structure & Tree travels

##### 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:

• 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:

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.