TREES

A TREE is a hierarchical, non-linear structure where data is organized in a parent-child relationship between nodes. It consists of nodes connected by edges, with a root node at the top and branches extending down to child nodes.

Easy Definition (Real-life Understanding):
A TREE is a way to show things that have a hierarchical structure — like a family TREE, or the folders inside a computer. Imagine an upside-down TREE 🌲 with one top point (called the root) and many branches growing downward. Each point (called a node) can have children (further branches), or none at all (these are leaves).

TREE in Data Structures (Technical Explanation):
A TREE in data structures is a non-linear data structure that is used to represent hierarchical relationships. It consists of nodes connected by edges. The topmost node is called the root. Each node can have zero or more child nodes.
A node with no children is called a leaf node. Every node (except the root) has exactly one parent.

Key Terms:
Root – The first/top node.
Parent – A node that has children.
Child – A node under a parent.
Leaf – A node with no children.
Edge – A connection between two nodes.
Subtree – A part of a TREE that is itself a tree.

INITIALIZATION - int arr[size] = {comma separated values};

TYPES OF TREES IN DATA STRUCTURES

Binary TREE – Each node has at most 2 children.
Binary Search TREE (BST) – A binary TREE where left < parent < right.
AVL TREE – A balanced BST.
Heap – A complete binary TREE with max/min at the root.
Trie – A TREE used for storing strings.

REAL LIFE EXAMPLE OF TREES

Imagine how your files are stored on your computer:
Root Folder = Main Drive (like C:/)
Inside it are Folders (like Documents, Pictures)
Inside Documents there may be more folders like Assignments, Projects
Inside those folders are files like project.docx, notes.txt
This creates a tree-like hierarchy.

REAL LIFE EXAMPLE - fruits = [name of fruits separated by commas];

FEATURES OF TREES

FEATURES OF ARRAYS - Same data type, Fixed size, Indexed access, Fast access, Efficient memory usage, Easy to loop through, Supports sorting and searching, Temporary storage in RAM, Can be multidimensional, Supported in most programming languages.

OPERATIONS IN AN TREES

INSERTION IN TREE

To insert a new node, we start from the root and find the correct position by comparing values (in BSTs) or adding as the next available child (in general TREE or heaps).

TIME COMPLEXITY - O(log n) in BST (balanced), O(n) in worst case

DELETION IN TREE

Removing a node involves three cases: node with no child (leaf), one child, or two children. In BSTs, we may need to replace it with in-order successor or predecessor.

TIME COMPLEXITY - O(log n) average, O(n) worst case

SEARCHING IN TREE

Searching means finding whether a value exists in the TREE. We start from the root and follow the structure (e.g. left or right based on value for BST).

TIME COMPLEXITY - O(log n) average, O(n) worst case

TRAVERSAL IN TREE

Traversal means visiting all nodes in a specific order:

  • Inorder (Left, Root, Right)
  • Preorder (Root, Left, Right)
  • Postorder (Left, Right, Root)
  • Level-order (Breadth-First)

TIME COMPLEXITY - O(n) for all traversals

HEIGHT OR DEPTH CALCULATION IN TREE

It calculates the height (longest path from root to a leaf) or depth (distance from root to a node) of the tree.

TIME COMPLEXITY - O(n)

FIND MIN/MAX IN BST

In a Binary Search Tree, minimum is the leftmost node, and maximum is the rightmost node.

TIME COMPLEXITY - O(log n) average, O(n) worst case

CODE CHEAT SHEETS FOR TREES

Download INSERTION CODE Sheet Download DELETION CODE Sheet Download SEARCHING CODE Sheet Download TRAVERSAL CODE Sheet Download HEIGHT/DEPTH Sheet Download MIN/MAX BST Sheet 

                

                

                

            

        

    


    

        
TREES COMPLEXITIES IN A GO...

        COMPLEXITIES - PREVIEW UNAVAILABLE
    

    

        HOME
        TOP OF THE PAGE