Essential Data Structures: Trees, Stacks, and Queues Explained

Posted on Oct 7, 2025 in Computers

Tree Data Structure and Terminology

A tree in data structures is a non-linear, hierarchical organization of data elements, called nodes, linked by edges. Trees are used to represent relationships where data is organized in levels.

Here are the key terminologies:

  • Node: A basic unit storing data and links to children.
  • Root: The topmost node; it has no parent.
  • Parent: A node with one or more children.
  • Child: A node directly connected below a parent.
  • Siblings: Nodes sharing the same parent.
  • Leaf: A node with no children (also called an external node).
  • Internal Node: A node with at least one child.
  • Edge: The link connecting a parent to a child node.
  • Path: A sequence of nodes and edges from one node to another.
  • Depth of a Node: The number of edges from the root to that node.
  • Height of a Node: The number of edges on the longest path from that node to a leaf.
  • Height of a Tree: The height of its root node.
  • Subtree: A node and all its descendants.
  • Degree of a Node: The number of direct children a node has.

Introduction to Binary Trees

A Binary Tree is a fundamental non-linear data structure in computer science where each node has at most two children, typically referred to as the left child and the right child. This constraint makes binary trees particularly useful for organizing data in a way that allows for efficient searching, insertion, and deletion operations.

Common terminologies specific to Binary Trees include: Root Node, Right Child, Left Child, Leaf Node, and Internal Node.

Types of Binary Trees

Full Binary Tree:
Every node has either zero or two children.
Complete Binary Tree:
All levels are completely filled, except possibly the last level, which is filled from left to right.
Perfect Binary Tree:
All internal nodes have two children, and all leaf nodes are at the same depth.
Skewed Binary Tree:
A tree where every node has only one child (either always left or always right).
Balanced Binary Tree:
A tree where the heights of the left and right subtrees of any node differ by at most one.

Binary Tree Traversal Rules

Preorder Traversal

Rule:

  1. Visit the Root node.
  2. Recursively traverse the Left subtree.
  3. Recursively traverse the Right subtree.

Inorder Traversal

Rule:

  1. Recursively traverse the Left subtree.
  2. Visit the Root node.
  3. Recursively traverse the Right subtree.

Postorder Traversal

Rule:

  1. Recursively traverse the Left subtree.
  2. Recursively traverse the Right subtree.
  3. Visit the Root node.


Stack Data Structure Definition

A Stack is a linear data structure that follows a particular order in which operations are performed. The order is LIFO (Last In, First Out) or FILO (First In, Last Out).

Applications of Stacks

Stacks are incredibly versatile and have numerous applications in computer science, including:

  • Function Call Management (Call Stack)
  • Expression Evaluation (e.g., infix to postfix conversion)
  • Undo/Redo Mechanisms
  • Browser History management
  • Recursion implementation
  • Backtracking Algorithms

Fundamental Operations on a Stack

These are the fundamental operations performed on a stack, typically implemented using arrays or linked lists:

  • push(): Insertion of an element onto the top of the stack.
  • pop(): Deletion and retrieval of the topmost element.
  • peek() / topElement(): Accessing or viewing the topmost element without removing it.
  • isEmpty(): Checking the status of the stack (returns true if empty).
  • isFull(): Checking the status of the stack (primarily for array-based implementations).

Array Implementation of a Stack

An array can be used to implement a stack by treating one end of the array as the “top” of the stack. This top pointer (usually an integer index) keeps track of the most recently added element.

Linked List Implementation of a Stack

A linked list provides a dynamic and flexible way to implement a stack, overcoming the fixed-size limitation of array-based stacks. In this approach, each element of the stack is represented by a node in a singly linked list, where insertion and deletion occur only at the head (top).

Queue Data Structure Definition

A Queue is a linear data structure that follows the First-In, First-Out (FIFO) principle. This means the element inserted first into the queue will be the first one to be removed.

Queues have two main ends:

  • Front (or Head): The end where elements are removed (Dequeue operation).
  • Rear (or Tail or Back): The end where new elements are added (Enqueue operation).

Basic Operations of a Queue

  • Enqueue: Adds an element to the rear of the queue.
  • Dequeue: Removes and returns the element from the front of the queue.
  • isEmpty: Checks if the queue is empty.
  • isFull: Checks if the queue is full (primarily for array-based implementations).
  • peek (or front): Returns the front element without removing it.

Key Applications of Queues

Queues are widely used in computing to manage sequential processes and resources where the order of arrival matters. Some common applications include:

  • CPU Scheduling
  • Printer Spooling
  • Buffering (e.g., I/O buffers)
  • Call Center Systems
  • Web Servers (managing requests)
  • Traffic Management (network packets)


Queue Array Implementation: Enqueue and Dequeue

In an array implementation of a queue, elements are managed using two pointers: front and rear.

  • Adding Elements (Enqueue/Insert): Elements are always added at the rear end of the queue.
  • Removing Elements (Dequeue/Delete): Elements are always removed from the front end of the queue.

Linked List Implementation of a Queue

A linked list implementation of a queue provides dynamic sizing. It typically maintains two pointers, one pointing to the front (for dequeue) and one pointing to the rear (for enqueue), ensuring that insertion and deletion operations remain efficient (O(1)).