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:

• 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