Introduction

Introduction to Trees

In the world of data structures and algorithms, understanding binary trees lays the groundwork for hierarchical organisation and efficient data manipulation.

Up until now, we have studied array, linked list, stack, and queues which are the fundamental linear data structures. Binary Trees are a different data structure and allow hierarchical organisation and structure of multi-level sequences. This resembles a tree with branching at each node expanding the tree in a non-linear fashion.

Binary Tree

Binary Tree: A fundamental hierarchical data structure in computer science that comprises nodes arranged in a tree-like structure. It consists of nodes, where each node can have at most two children nodes, known as the left child and the right child.

Nodes: Each node in a binary tree contains a piece of data, often referred to as the node’s value or key. This node also contains references and pointers to its left and right children so that we can traverse from one node to another in a hierarchical order.

Root Node

Root Node: The topmost node of a binary tree from which all other nodes stem out. This serves as the entry point for traversing the tree structure.

Children Nodes

Children Nodes: Nodes directly connected to a parent node. In a binary tree, a parent node can have zero, one, or two children nodes, each situated to the left or right of the parent node.

Leaf Nodes: Nodes that do not have any children. These nodes lie on the outermost ends of the tree branches and are the terminal points of the traversal.

Ancestors

Ancestors: Nodes that lie on the path from a particular node to the root node. They are the nodes encountered while moving upwards from a specific node through its parent nodes until reaching the root of the tree.

Full Binary Tree

Full Binary Tree: Also known as a Strict Binary Tree, where every node has either zero or two children. No node of this tree has just a single child; all internal nodes have exactly two children or no children if they are leaf nodes.

The property that each node has either 2 or 0 children contributes significantly to the tree’s balance, making traversal, searching, and insertion options more predictable and efficient. The emphasis on having exactly two children optimises space utilisation and makes the tree more balanced.

Complete Binary Tree

Complete Binary Tree: A specialised form of Binary Tree where all levels are filled completely except possibly the last level, which is filled from left to right. All levels of the tree, except possibly the last one, are fully filled. If the last level is not completely filled, it is filled from left to right, ensuring that nodes are positioned as far left as possible.

In a complete binary tree, all leaf nodes are in the last level or the second-to-last level, and they are positioned towards the leftmost side.

This structure is particularly useful for storing data in structures like heaps, where efficient access to the top element (root) or certain properties (e.g., maximum or minimum values in a heap) is crucial. The completeness property aids in achieving balanced structures, making it easier to implement algorithms and ensuring reasonably consistent performance.

Although it might seem similar to a full binary tree, a complete binary tree doesn't require all nodes to have two children; it's about the positioning and arrangement of nodes.

Perfect Binary Tree

Perfect Binary Tree: A type of Binary Tree where all leaf nodes are at the same level and the number of leaf nodes is maximised for that level. Every node in a perfect binary tree has either zero or two children. This means that every internal node (non-leaf node) has exactly two children and all leaf nodes are at the same level.

All levels of this tree are fully filled with nodes including the last level. Perfect Binary Trees have a balanced structure that maximises the number of nodes for a given height, creating a dense structure where the number of nodes doubles as we move down each level of the tree.

Properties of perfect binary trees make them efficient for certain operations like searching and sorting due to their balanced nature. However, achieving and maintaining perfect balance, especially when the number of nodes is not a power of two, might not be feasible in many practical applications.

Balanced Binary Tree

Balanced Binary Tree: A type of Binary Tree where the heights of the two subtrees of any node differ by at most one. This property ensures that the tree remains relatively well-balanced, preventing the tree from becoming highly skewed or degenerate.

In a balanced binary tree, the height of the tree should be log2N at maximum, where N is the number of nodes. This ensures that the tree does not become heavily skewed or imbalanced. The distribution of nodes of both the left and right subtrees remains relatively even throughout the tree.

Degenerate Tree

Degenerate Tree: A Binary Tree where the nodes are arranged in a single path leaning to the right or left. The tree resembles a linked list in its structure where each node points to the next node in a linear fashion.

Each level of this tree only has one node. The height of the tree reaches ‘n’, i.e., the number of nodes in the tree, resulting in inefficient search operations. Though degenerate trees are not commonly used intentionally due to their inefficient nature for most operations, they may occur inadvertently in scenarios where nodes are inserted in a specific order (e.g., always to the right or left), causing the tree to lose its balanced properties.

Understanding degenerate trees is essential in analysing the worst-case time complexity of algorithms in scenarios where the tree structure degrades to this linear form, as it can help in optimising algorithms for these situations.

In Summary

In summary, Binary Trees introduce a hierarchical arrangement taking a step ahead of the linear structure we have studied so far.

Binary Trees comprise nodes, each capable of hosting at most two children hence the predecessor ‘Binary’. These structures mirror the hierarchical organisation seen in file systems.

Full Binary Trees impose the constraint that each node possesses either zero or two children, promoting a well-balanced structure and enhancing predictability in operations like traversal and insertion.

Complete Binary Trees embrace a specialised form where all levels, save possibly the last, are completely filled. Their design ensures nodes are positioned leftmost on the last level, proving valuable for efficient data storage and access, resembling the organised arrangement of folders and files in a computer system.

Perfect Binary Trees showcase a balanced structure where all leaf nodes align at the same level. Such trees optimise space by filling all levels with nodes, creating a dense structure.

Balanced Binary Trees ensure the difference in heights between subtrees of any node remains minimal, preventing significant skewing or imbalance.

Degenerate Trees represent a case where nodes arrange linearly, akin to a linked list, posing inefficiencies in search operations due to the lack of balance.

Binary Tree Presentation in C++

In C++, a binary tree is represented using pointers, forming a hierarchical structure where each node can point to two further nodes: a left child and a right child. This representation uses pointers to establish connections between nodes in the tree, allowing traversal and navigation throughout the structure.

Node Structure: A binary tree node is represented using a struct or class that contains the following components:

• Data Component: Holds the value of the node, which could be of any data type (e.g., integer, string, object).
• Pointers to Children: Two pointers, left and right, pointing to the left and right child nodes, respectively. These pointers store the memory addresses of the child nodes, allowing navigation and access to further nodes in the tree.

Node Constructor: The constructor function is named Node, which is the same as the structure name. It takes an integer val as a parameter, which represents the value to be stored in the node.

• data = val; : Assigns the value passed as a parameter (val) to the data member of the node. This sets the value of the node to the input integer.
• left = right = NULL; : Initialises both the left and right pointers to NULL. This is done to ensure that initially, the node does not have any left or right children. Setting pointers to NULL indicates that there are no connections to other nodes at the time of node creation.

Node Connection: When constructing a binary tree using pointers, each node stores references (memory addresses) to its left and right children. These references form the connections between nodes, enabling the hierarchical structure.

When creating a new node, memory is allocated, and the node's data is stored. Pointers left and right are initialised as nullptr (in C++) or NULL to signify that the node currently has no children. Later, nodes are connected by assigning the left and right pointers of a parent node to the memory addresses of its respective left and right child nodes.

#include <iostream>

// Structure definition for
// a node in a binary tree
struct Node {
    // Defining the value of
    // the node (integer data)
    int data;        
     // Reference pointer to
     // the left child node
    Node* left;      
    // Reference pointer to
    // the right child node
    Node* right;      

    // Method to initialize
    // the node with a value
    Node(int val) {
        // Set the value of the
        // node to the passed integer
        data = val;   
        // Initialize left and 
        //r ight pointers as NULL
        left = right = NULL;  
    }
};

int main() {
    // Creating a new node for the root of the 
    // binary tree using dynamic allocation
    Node* root = new Node(1);
    // Creating left and right child
    // nodes for the root node
    root->left = new Node(2);
    root->right = new Node(3);
    // Creating a right child node for
    // the left child node of the root
    root->left->right = new Node(5);
}

Binary Tree Presentation in Java

In Java, a binary tree is structured using references to other nodes, forming a hierarchical arrangement where each node can refer to at most two other nodes: a left child and a right child. This reference-based approach establishes connections between nodes, enabling traversal and navigation within the tree structure.

Node Structure: In Java, a Binary Tree node is represented using a class that encapsulates the attributes of a node:

• Data Component: Holds the value of the node which can be of any data type (e.g., int, string, custom object).
• References to Children: Two reference variables, 'left' and 'right', point to the left and right child nodes respectively. These references store the memory addresses of child nodes, allowing traversal and access to further nodes in the tree structure.

In Java, references to objects act similarly to pointers in C++, allowing nodes to refer to other nodes without direct memory manipulation.

Node Constructor: In Java, the constructor of the Node class initialises a node with a specific value and sets its left and right references to null to signify that it doesn't have any children initially.

• data = val; : Sets the data of the node to the provided value (val). This assigns the input integer to the node's data.
• left = right = NULL; : Initialises both left and right references as null. This initialization ensures that when a node is created, it does not have any immediate connections to other nodes, indicating the absence of left and right children.

Node Connection: Java utilises references between nodes allowing them to refer to other nodes. When creating a new node, memory is allocated for the node object, and the node’s data is stored within it. References ('left' and 'right') are initialised as 'null' to indicate that the node doesn’t currently have any children. The nodes are connected by assigning references of a parent node to its respective left and right child nodes.

class Node {
    // Stores the value
    // of the node
    int data;       
    // Reference to the
    // left child node
    Node left; 
    // Reference to the
    // right child node
    Node right;

    // Constructor to initialize
    // a node with a given key
    public Node(int key) {
        // Assigns the provided key to
        // the data field of the node
        data = key;     
        // Initializes left child 
        // reference as null
        left = null;    
        // Initializes right child
        // reference as null
        right = null;   
    }
}

public class Main {
    public static void main(String[] args) {
         // Creates the root node
         // with a key value of 1
        Node root = new Node(1);       
        // Creates a left child node for
        // the root with a key value of 2
        root.left = new Node(2);       
         // Creates a right child node for
         // the root with a key value of 3
        root.right = new Node(3);      
         // Creates a left child node for the right 
         // child of the root with a key value of 5
        root.right.left = new Node(5); 
    }
}