Data Structures Tutorial

Data Structures Tutorial Asymptotic Notation Structure and Union Array Data Structure Linked list Data Structure Type of Linked list Advantages and Disadvantages of linked list Queue Data Structure Implementation of Queue Stack Data Structure Implementation of Stack Sorting Insertion sort Quick sort Selection sort Heap sort Merge sort Bucket sort Count sort Radix sort Shell sort Tree Traversal of the binary tree Binary search tree Graph Spanning tree Linear Search Binary Search Hashing Collision Resolution Techniques

Misc Topic:

Priority Queue in Data Structure Deque in Data Structure Difference Between Linear And Non Linear Data Structures Queue Operations In Data Structure About Data Structures Data Structures Algorithms Types of Data Structures Big O Notations Introduction to Arrays Introduction to 1D-Arrays Operations on 1D-Arrays Introduction to 2D-Arrays Operations on 2D-Arrays Strings in Data Structures String Operations Application of 2D array Bubble Sort Insertion Sort Sorting Algorithms What is DFS Algorithm What Is Graph Data Structure What is the difference between Tree and Graph What is the difference between DFS and BFS Bucket Sort Dijkstra’s vs Bellman-Ford Algorithm Linear Queue Data Structure in C Stack Using Array Stack Using Linked List Recursion in Fibonacci Stack vs Array What is Skewed Binary Tree Primitive Data Structure in C Dynamic memory allocation of structure in C Application of Stack in Data Structures Binary Tree in Data Structures Heap Data Structure Recursion - Factorial and Fibonacci What is B tree what is B+ tree Huffman tree in Data Structures Insertion Sort vs Bubble Sort Adding one to the number represented an array of digits Bitwise Operators and their Important Tricks Blowfish algorithm Bubble Sort vs Selection Sort Hashing and its Applications Heap Sort vs Merge Sort Insertion Sort vs Selection Sort Merge Conflicts and ways to handle them Difference between Stack and Queue AVL tree in data structure c++ Bubble sort algorithm using Javascript Buffer overflow attack with examples Find out the area between two concentric circles Lowest common ancestor in a binary search tree Number of visible boxes putting one inside another Program to calculate the area of the circumcircle of an equilateral triangle Red-black Tree in Data Structures Strictly binary tree in Data Structures 2-3 Trees and Basic Operations on them Asynchronous advantage actor-critic (A3C) Algorithm Bubble Sort vs Heap Sort Digital Search Tree in Data Structures Minimum Spanning Tree Permutation Sort or Bogo Sort Quick Sort vs Merge Sort Boruvkas algorithm Bubble Sort vs Quick Sort Common Operations on various Data Structures Detect and Remove Loop in a Linked List How to Start Learning DSA Print kth least significant bit number Why is Binary Heap Preferred over BST for Priority Queue Bin Packing Problem Binary Tree Inorder Traversal Burning binary tree Equal Sum What is a Threaded Binary Tree? What is a full Binary Tree? Bubble Sort vs Merge Sort B+ Tree Program in Q language Deletion Operation from A B Tree Deletion Operation of the binary search tree in C++ language Does Overloading Work with Inheritance Balanced Binary Tree Binary tree deletion Binary tree insertion Cocktail Sort Comb Sort FIFO approach Operations of B Tree in C++ Language Recaman’s Sequence Tim Sort Understanding Data Processing Applications of trees in data structures Binary Tree Implementation Using Arrays Convert a Binary Tree into a Binary Search Tree Create a binary search tree Horizontal and Vertical Scaling Invert binary tree LCA of binary tree Linked List Representation of Binary Tree Optimal binary search tree in DSA Serialize and Deserialize a Binary Tree Tree terminology in Data structures Vertical Order Traversal of Binary Tree What is a Height-Balanced Tree in Data Structure Convert binary tree to a doubly linked list Fundamental of Algorithms Introduction and Implementation of Bloom Filter Optimal binary search tree using dynamic programming Right side view of binary tree Symmetric binary tree Trim a binary search tree What is a Sparse Matrix in Data Structure What is a Tree in Terms of a Graph What is the Use of Segment Trees in Data Structure What Should We Learn First Trees or Graphs in Data Structures All About Minimum Cost Spanning Trees in Data Structure Convert Binary Tree into a Threaded Binary Tree Difference between Structured and Object-Oriented Analysis FLEX (Fast Lexical Analyzer Generator) Object-Oriented Analysis and Design Sum of Nodes in a Binary Tree What are the types of Trees in Data Structure What is a 2-3 Tree in Data Structure What is a Spanning Tree in Data Structure What is an AVL Tree in Data Structure Given a Binary Tree, Check if it's balanced B Tree in Data Structure Convert Sorted List to Binary Search Tree Flattening a Linked List Given a Perfect Binary Tree, Reverse Alternate Levels Left View of Binary Tree What are Forest Trees in Data Structure Compare Balanced Binary Tree and Complete Binary Tree Diameter of a Binary Tree Given a Binary Tree Check the Zig Zag Traversal Given a Binary Tree Print the Shortest Path Given a Binary Tree Return All Root To Leaf Paths Given a Binary Tree Swap Nodes at K Height Given a Binary Tree Find Its Minimum Depth Given a Binary Tree Print the Pre Order Traversal in Recursive Given a Generate all Structurally Unique Binary Search Trees Perfect Binary Tree Threaded Binary Trees Function to Create a Copy of Binary Search Tree Function to Delete a Leaf Node from a Binary Tree Function to Insert a Node in a Binary Search Tree Given Two Binary Trees, Check if it is Symmetric A Full Binary Tree with n Nodes Applications of Different Linked Lists in Data Structure B+ Tree in Data Structure Construction of B tree in Data Structure Difference between B-tree and Binary Tree Finding Rank in a Binary Search Tree Finding the Maximum Element in a Binary Tree Finding the Minimum and Maximum Value of a Binary Tree Finding the Sum of All Paths in a Binary Tree Time Complexity of Selection Sort in Data Structure How to get Better in Data Structures and Algorithms Binary Tree Leaf Nodes Classification of Data Structure Difference between Static and Dynamic Data Structure Find the Union and Intersection of the Binary Search Tree Find the Vertical Next in a Binary Tree Finding a Deadlock in a Binary Search Tree Finding all Node of k Distance in a Binary Tree Finding Diagonal Sum in a Binary Tree Finding Diagonal Traversal of The Binary Tree Finding In-Order Successor Binary Tree Finding the gcd of Each Sibling of the Binary Tree Greedy Algorithm in Data Structure How to Calculate Space Complexity in Data Structure How to find missing numbers in an Array Kth Ancestor Node of Binary Tree Minimum Depth Binary Tree Mirror Binary Tree in Data Structure Red-Black Tree Insertion Binary Tree to Mirror Image in Data Structure Calculating the Height of a Binary Search Tree in Data Structure Characteristics of Binary Tree in Data Structure Create a Complete Binary Tree from its Linked List Field in Tree Data Structure Find a Specified Element in a binary Search Tree Find Descendant in Tree Data Structure Find Siblings in a Binary Tree Given as an Array Find the Height of a Node in a Binary Tree Find the Second-Largest Element in a Binary Tree Find the Successor Predecessor of a Binary Search Tree Forest of a Tree in Data Structure In Order Traversal of Threaded Binary Tree Introduction to Huffman Coding Limitations of a Binary Search Tree Link State Routing Algorithm in Data Structure Map Reduce Algorithm for Binary Search Tree in Data Structure Non-Binary Tree in Data Structure Quadratic Probing Example in Hashing Scope and Lifetime of Variables in Data Structure Separate Chaining in Data Structure What is Dynamic Data Structure Separate Chaining vs Open Addressing Time and Space Complexity of Linear Data Structures Abstract Data Types in Data Structures Binary Tree to Single Linked List Count the Number of Nodes in the Binary Tree Count Total No. of Ancestors in a Binary Search Tree Elements of Dynamic Programming in Data Structures Find cost of tree with prims algorithm in data structures Find Preorder Successor in a Threaded Binary Tree Find Prime Nodes Sum Count in Non-Binary Tree Find the Right Sibling of a Binary Tree with Parent Pointers Find the Width of the Binary Search Tree Forest trees in Data Structures Free Tree in Data Structures Frequently asked questions in Tree Data Structures Infix, Postfix and Prefix Conversion Time Complexity of Fibonacci Series What is Weighted Graph in Data Structure What is the Advantage of Linear Search?

Tree terminology in Data structures
2022-10-23 03:52:48

Tree terminology in Data structures

Data structures

The storage used to organize and store data is known as a data structure, and it is a method where data can be arranged on a computer to be updated or accessed proficiently. A data model is a database used to store and manage data and is a system for optimizing and managing computer resources. Data structures are not just for storing data. Almost every program or application has a basic and advanced data structure. We have many basic and advanced types of data structures, and it is hard to find a program without data structures in any programming language.

Data structures are forms used to store, process, organize and retrieve data proficiently and quickly in a specific format on a machine or computer. Data structures help render data for easy use and handling of information. Any program foundation, software, or application consists of two components: data and algorithms—the communication of information and the rules and regulations of the algorithm that turn information into action.

We can depict all the above in the following two simple equations:

Operations that are permissible on the data + Related data = Data Structure

Algorithms + Data structures = Programs

There are two types of data structures:

  • Linear Data structures
  • Non-linear data structures

Linear Data structures

This type of data structure adds information to the data model. Each element is related to the component before and after. So, you can remove the instance. There are four types of this data structure. They are:

  • Queue
  • Stack
  • Linked lists
  • Array

Non-linear Data structures

A data structure in which data elements are organized in different ways. Content is not a series of data presented at different levels. There are several ways to move directly from one element to another. Unauthorized data points are shared at least once. There are two types of this non-linear data structure. They are:

  • Tree data structure
  • Graph data structure

Tree Data structure

A tree is a hierarchical and non-linear data structure with nodes. Each node in the Tree contains a message value and stores the name passed to another ("child") node.

Organizing these files is a great way to collect your information and make it easy to reference on your computer. The tree data structure consists of sub-nodes, structural nodes, and a central node connected by the edges, and this data structure also has leaves, branches, and roots attached.

The data in the Tree is plotted so that it is not linear. But they are organized differently, or we can say hierarchically. The trees are considered non-linear as they are hierarchical.

Tree data structures differ from queues, stacks, arrays, and linked lists. A tree is a hierarchical structure; data structures have nodes representing and supporting the process. Asynchronous Data Warehouse Tree types collect different levels of information together in a data structure called a root node. All data types are stored in the root location. Each line has a message. We call the branches of the data structure at the bottom of the Tree.

There is a particular type of Tree called the Binary tree. It is used for the same data storage purposes and is a unique data structure. This data structure is a particular tree as it can have only a maximum number of two children, i.e., a binary tree can either have 0, 1, or 2 children at any stage. This allows the binary Tree to provide the benefits of an ordinary linked list and array, making searching an element stored easy (as they are sorted data structures). A binary search tree can perform the deletion and insertion of elements competing with the speed of linked lists.

Tree terminology in data structures

Before understanding any concept, we must be familiar with the language usually used in the topic. The tree concept of data structures uses pretty simple and straightforward terminology. Hence, below are the basic terminology traditionally used in the tree data structure concept.

  1. Node
  2. Root
  3. Edge
  4. Parent
  5. Child
  6. Siblings
  7. Neighbour node
  8. Leaf
  9. Internal nodes
  10. External nodes
  11. Ancestors
  12. Descendants
  13. Degree
  14. Level
  15. Height
  16. Depth
  17. Path
  18. Subtree

Node

The entities, values, or keys stored in a tree data structure are known as Nodes. It is, in fact, the place where we place our information or data in a tree data structure.

Tree terminology in Data structures

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, and 12 are the nodes in the above Tree.

Edge

An edge is a connection among given consecutive nodes in a tree data structure. The nodes and edges together make a tree data structure. Nodes and edges are the only two factors that can be found in any tree data structure. We can say that without these two, a data structure cannot be treated as a tree. Edges are represented by straight lines connecting two nodes.

Tree terminology in Data structures

The black lines in the above Tree are its edges.

Root Node

The node that lies at the peak of the tree data structure is known as the root node. The root node only has child nodes, and it does not have any parent nodes. The formation of a tree data structure starts from the root node, and any tree data structure has only one root node. That data structure cannot be treated as a tree if there is more than one root node.

Tree terminology in Data structures

The root node in the above tree is 1.

Parent Node

The node above any node in a tree data structure is treated as its parent node. Any node in a tree data structure can have only one parent node.

Tree terminology in Data structures

For example, 2 is the parent node of 5 and 6.

Child node

The node below any given node in a tree data structure is treated as its parent node. Any node in a tree data structure can have any number of child nodes, and leaf nodes do not have child nodes. A child node may or may not have further child nodes but must have a parent node. If any node in a tree data structure does not have a parent node, then it cannot be treated as a child node.

Tree terminology in Data structures

For example, 7 and 8 are the child nodes of 4.

Siblings

Child nodes of one parent node are called sibling nodes. As the name suggests, sibling nodes share a single parent.

Tree terminology in Data structures

For example, 9 and 10 are sibling nodes.

Neighbour node

Any two nodes directly connected by a single edge are called neighbour nodes. For any given node in a tree data structure, its respective parent node and child nodes can be treated as neighbour nodes.

Tree terminology in Data structures

For example, 2, 9, and 10 are the neighbour nodes of 5.

Leaf node

The nodes that do not have child nodes are called leaf nodes or terminal nodes, and they put an end to their respective branch of the tree data structure.

Tree terminology in Data structures

9, 10, 6, 3, 11, 12, and 8 are the leaf nodes.

Internal nodes

All the nodes in a tree data structure, excluding the root and leaf nodes, are treated as internal nodes.

Tree terminology in Data structures

2, 4, 5, and 7 are the internal nodes.

External nodes

All the leaf nodes and root nodes in a given tree data structure are called external nodes.

Tree terminology in Data structures

1, 9, 10, 6, 3, 11, 12, and 8 are the external nodes.

Ancestors

All the nodes that precede a given node in a tree data structure are treated as ancestor nodes to that node. 

Tree terminology in Data structures

For example, 5, 2, and 1 are the ancestors of 10.

Descendants

All the nodes that lie below a given node in a tree data structure are treated as the descendant nodes of that node.

Tree terminology in Data structures

For example, 7, 8, 11, and 12 are the descendants of 4.

Degree

The number of child nodes of a given node in a tree data structure is called the Degree of that node. The Degree of the node with the highest Degree among all other degrees in a given tree data structure is treated as the Degree of the Tree.

Tree terminology in Data structures

For example, a degree of 7 is 2.

Level

The level of a given node in a tree data structure is the number of edges that connect it to the root node. Root node's child nodes have a level equal to 1; their child nodes have a level equivalent to 2.

Tree terminology in Data structures

For example, a level of 6 is 2.

Height

In a tree data structure, the level of a node is calculated starting from the root node, while its height is calculated starting from leaf nodes. The height of any leaf node in a tree data structure is equal to zero.

Tree terminology in Data structures

For example, the height of 4 is 2.

Depth

The depth of a given node in a tree data structure is the number of edges that connect it to the root node. The largest tree data structure's largest depth is treated as that Tree's depth. The largest depth is equal to the depth of the leaf node with the longest path from the root node.

Tree terminology in Data structures

For example, a depth of 5 is 2.

Path

The sequence of edges and nodes between any two selected nodes in a tree data structure is called the path between the given nodes. We can only have a single path between two nodes in a tree data structure.

Tree terminology in Data structures

For example, the path between 6 and 7 is

Tree terminology in Data structures

Subtree

Any node under the root node, along with its chosen descendants, is known as a subtree.

Tree terminology in Data structures

An example of a subtree for the above tree is

Tree terminology in Data structures